/*************************************
* author: marvinthang *
* created: 20.04.2023 11:09:59 *
*************************************/
#include "mars.h"
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define left ___left
#define right ___right
#define TIME (1.0 * clock() / CLOCKS_PER_SEC)
#define MASK(i) (1LL << (i))
#define BIT(x, i) ((x) >> (i) & 1)
#define __builtin_popcount __builtin_popcountll
#define ALL(v) (v).begin(), (v).end()
#define REP(i, n) for (int i = 0, _n = (n); i < _n; ++i)
#define REPD(i, n) for (int i = (n); i--; )
#define FOR(i, a, b) for (int i = (a), _b = (b); i < _b; ++i)
#define FORD(i, b, a) for (int i = (b), _a = (a); --i >= _a; )
#define FORE(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i)
#define FORDE(i, b, a) for (int i = (b), _a = (a); i >= _a; --i)
#define scan_op(...) istream & operator >> (istream &in, __VA_ARGS__ &u)
#define print_op(...) ostream & operator << (ostream &out, const __VA_ARGS__ &u)
#ifdef LOCAL
#include "debug.h"
#else
#define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
#define DB(...) 23
#define db(...) 23
#define debug(...) 23
#endif
template <class U, class V> scan_op(pair <U, V>) { return in >> u.first >> u.second; }
template <class T> scan_op(vector <T>) { for (size_t i = 0; i < u.size(); ++i) in >> u[i]; return in; }
template <class U, class V> print_op(pair <U, V>) { return out << '(' << u.first << ", " << u.second << ')'; }
template <size_t i, class T> ostream & print_tuple_utils(ostream &out, const T &tup) { if constexpr(i == tuple_size<T>::value) return out << ")"; else return print_tuple_utils<i + 1, T>(out << (i ? ", " : "(") << get<i>(tup), tup); }
template <class ...U> print_op(tuple<U...>) { return print_tuple_utils<0, tuple<U...>>(out, u); }
template <class Con, class = decltype(begin(declval<Con>()))> typename enable_if <!is_same<Con, string>::value, ostream&>::type operator << (ostream &out, const Con &con) { out << '{'; for (__typeof(con.begin()) it = con.begin(); it != con.end(); ++it) out << (it == con.begin() ? "" : ", ") << *it; return out << '}'; }
// end of template
const int dx[] = {0, 1, 0, -1};
const int dy[] = {1, 0, -1, 0};
string process(vector <vector <string>> h, int i, int j, int k, int n) {
int m = 2 * (n - k - 1);
int sz = 2 * n + 1;
string res(100, '0');
vector board(sz, vector<char>(sz, '0'));
vector comps(sz, vector<int>(sz));
vector adj(sz, vector(sz, vector<pair<int, int>>()));
auto bfs = [&] (int sx, int sy, int cl) {
queue <pair <int, int>> q;
q.emplace(sx, sy);
comps[sx][sy] = cl;
while (!q.empty()) {
auto [x, y] = q.front(); q.pop();
REP(d, 4) {
int u = x + dx[d];
int v = y + dy[d];
if (u < 0 || v < 0 || u >= sz || v >= sz || board[u][v] == '0' || comps[u][v]) continue;
comps[u][v] = cl;
q.emplace(u, v);
}
for (auto [u, v]: adj[x][y]) {
if (board[u][v] == '0' || comps[u][v]) continue;
comps[u][v] = cl;
q.emplace(u, v);
}
}
};
auto toBinary = [&] (int v, int len) {
string res;
REP(i, len) {
res += '0' + (v & 1);
v >>= 1;
};
return res;
};
auto toDecimal = [&] (const string &s, int l, int len) {
int res = 0;
FORD(i, l + len, l) res = res << 1 | (s[i] == '1');
return res;
};
auto getBorder = [&] (int i, int j) {
vector <pair <int, int>> res;
if (!i) {
if (!j) {
REP(i, n + 1) res.emplace_back(n, i);
REPD(i, n) res.emplace_back(i, n);
} else {
FORD(i, sz, n) res.emplace_back(n, i);
REPD(i, n) res.emplace_back(i, n);
}
} else {
if (!j) {
REP(i, n) res.emplace_back(n, i);
FOR(i, n, sz) res.emplace_back(i, n);
} else {
FORD(i, sz, n) res.emplace_back(n, i);
FOR(i, n + 1, sz) res.emplace_back(i, n);
}
}
return res;
};
if (n == 1) {
int cl = 0;
REP(x, sz) REP(y, sz) board[x][y] = h[x][y][0];
REP(x, sz) REP(y, sz) if (board[x][y] == '1' && !comps[x][y]) {
++cl;
bfs(x, y, cl);
}
return toBinary(cl, 100);
}
if (k == n - 1) {
int res = 0;
for (int i: {0, 2}) for (int j: {0, 2}) {
res += toDecimal(h[i][j], 83, 17);
vector border(getBorder(i, j));
string mask = h[i][j].substr(0, 41);
vector <int> head;
REP(i, border.size()) {
auto [x, y] = border[i];
if (mask[i] == '1') {
board[x][y] = '1';
if (!i || mask[i - 1] == '0') head.push_back(i);
}
}
string open(h[i][j].substr(41, 21)), close(h[i][j].substr(62, 21));
stack <pair <int, int>> st;
REP(i, head.size()) {
int p = head[i];
auto [x, y] = border[p];
if (open[i] == '1') st.emplace(x, y);
else {
auto [u, v] = st.top();
adj[x][y].emplace_back(u, v);
adj[u][v].emplace_back(x, y);
}
if (close[i] == '1') st.pop();
}
}
REP(x, sz) REP(y, sz) if (board[x][y] == '1' && !comps[x][y]) {
++res;
bfs(x, y, res);
}
return toBinary(res, 100);
}
auto get_first = [&] (int i, int k) {
if (k == n - 1) return !i ? 0 : i == 1 ? n + 1 : i == 2 ? n : sz;
return min(max(i, i * n / 2), i + 2 * k);
};
int li = get_first(i, k + 1), lj = get_first(j, k + 1);
int ri = get_first(i + 1, k + 1), rj = get_first(j + 1, k + 1);
REP(tx, 3) REP(ty, 3) {
int lx = get_first(i + tx, k), ly = get_first(j + ty, k);
int rx = get_first(i + tx + 1, k), ry = get_first(j + ty + 1, k);
FOR(x, lx, rx) FOR(y, ly, ry) board[x][y] = h[tx][ty][(x - lx) * 10 + (y - ly)];
}
if (k == n - 2) {
if (i & 1 || j & 1) return res;
REP(x, sz) REP(y, sz) if (x < li || x >= ri || y < lj || y >= rj) board[x][y] = '0';
vector border(getBorder(i, j));
int cl = 0;
for (auto [x, y]: border) if (board[x][y] == '1' && !comps[x][y]) {
++cl;
bfs(x, y, cl);
}
int res = 0;
FOR(x, li, ri) FOR(y, lj, rj) if (board[x][y] == '1' && !comps[x][y]) {
++res;
bfs(x, y, res);
}
bool first = true;
string mask(41, '0');
vector <int> head;
REP(i, border.size()) {
auto [x, y] = border[i];
if (board[x][y] == '1') {
mask[i] = '1';
if (!i || board[border[i - 1].fi][border[i - 1].se] == '0') head.push_back(i);
}
}
string open(21, '0'), close(21, '0');
vector <bool> used(cl + 1);
REP(i, head.size()) {
int p = head[i];
auto [x, y] = border[p];
if (!used[comps[x][y]]) {
used[comps[x][y]] = true;
open[i] = '1';
}
}
REPD(i, head.size()) {
int p = head[i];
auto [x, y] = border[p];
if (used[comps[x][y]]) {
used[comps[x][y]] = false;
close[i] = '1';
}
}
return mask + open + close + toBinary(res, 17);
}
int cur = 0;
FOR(x, li, ri) FOR(y, lj, rj) res[(x - li) * 10 + (y - lj)] = board[x][y];
return res;
}
#ifdef LOCAL
#include "mars.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
#include <string>
#include <bitset>
using namespace std;
static void WA(string msg)
{
cout << "WA: " << msg << endl;
exit(0);
}
static long long to_longlong(string s)
{
long long ans=0;
for(int i=(int)s.size()-1;i>=0;i--)
ans=(ans*2)+s[i]-'0';
return ans;
}
int main()
{
ios_base::sync_with_stdio(false);
file("mars");
int t;
assert(scanf("%d",&t) == 1);
while(t--)
{
int n;
assert(scanf("%d",&n) == 1);
vector <vector<char>> s(2*n+1, vector<char>(2*n+1));
for(int i = 0; i < 2*n+1; i++) {
for(int j = 0; j < 2*n+1; j++) {
assert(scanf(" %c",&s[i][j]) == 1);
// cout << s[i][j] << ' ';
}
// cout << '\n';
}
// cout << string(10, '=') << '\n';
vector <vector<string>> h(2*n+1, vector<string>(2*n+1, string(100 ,'0')));
for(int i = 0; i < 2*n+1; i++)
for(int j = 0; j < 2*n+1; j++)
h[i][j][0] = s[i][j];
vector <vector<string>> subarr(3, vector<string>(3));
for(int k = 0; k < n; k++)
{
int m = 2*(n-k-1);
for(int i = 0; i <= m; i++)
{
for(int j = 0; j <= m; j++)
{
for(int y = 0; y < 3; y++)
{
for(int x = 0; x < 3; x++)
{
subarr[y][x] = h[i+y][j+x];
}
}
h[i][j] = process(subarr, i, j, k, n);
if(h[i][j].size() != 100) WA("Invalid return length");
for(int l = 0; l < 100; l++)
if(h[i][j][l] != '0' && h[i][j][l] != '1') WA("Invalid return");
}
}
}
cout << to_longlong(h[0][0]) << '\n';
}
}
#endif
