#include <bits/stdc++.h>
using namespace std;
#ifdef tabr
#include "library/debug.cpp"
#else
#define debug(...)
#endif
struct dsu {
vector<int> p;
vector<int> sz;
int n;
dsu(int _n) : n(_n) {
p = vector<int>(n);
iota(p.begin(), p.end(), 0);
sz = vector<int>(n, 1);
}
inline int get(int x) {
if (p[x] == x) {
return x;
} else {
return p[x] = get(p[x]);
}
}
inline bool unite(int x, int y) {
x = get(x);
y = get(y);
if (x == y) {
return false;
}
p[x] = y;
sz[y] += sz[x];
return true;
}
inline bool same(int x, int y) {
return (get(x) == get(y));
}
inline int size(int x) {
return sz[get(x)];
}
inline bool root(int x) {
return (x == get(x));
}
};
string count_islands(vector<string> s) {
int n = (int) s.size();
dsu uf(n * n);
for (int i = 0; i < n; i++) {
for (int j = 0; j < n - 1; j++) {
if (s[i][j] == '1' && s[i][j + 1] == '1') {
uf.unite(i * n + j, i * n + j + 1);
}
}
}
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n; j++) {
if (s[i][j] == '1' && s[i + 1][j] == '1') {
uf.unite(i * n + j, i * n + j + n);
}
}
}
int ans = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (s[i][j] == '1' && uf.root(i * n + j)) {
ans++;
}
}
}
string res(100, '0');
for (int i = 0; i < 20; i++) {
if (ans & (1 << i)) {
res[i] = '1';
}
}
return res;
}
vector<int> count_groups(int k, int n) {
if (k == 0) {
vector<int> g;
for (int i = 0; i < 3; i++) {
g.emplace_back((2 * n + 1) * (i + 1) / 3 - (2 * n + 1) * i / 3);
}
return g;
}
auto g = count_groups(k - 1, n);
for (int z = 0; z < 2; z++) {
for (int i = 0; i < 3; i++) {
if (g[i] > 1) {
g[i]--;
break;
}
}
}
return g;
}
vector<int> move_from(int k, int n) {
assert(0 <= k && k < n - 1);
auto g = count_groups(k, n);
int l = 2 * (n - k) - 1;
vector<int> c;
assert(g[0] + g[1] + g[2] == l + 2);
for (int z = 0; z < 2; z++) {
for (int i = 0; i < 3; i++) {
if (g[i] > 1) {
g[i]--;
c.emplace_back(i);
break;
}
}
}
for (int i = 0; i < 2; i++) {
c[i] = g[c[i]];
}
for (int i = 0; i < l; i++) {
c.emplace_back(i);
}
sort(c.begin(), c.end());
return c;
}
vector<vector<vector<pair<int, int>>>> original_pos(int k, int n) {
int l = 2 * (n - k) + 1;
vector<vector<vector<pair<int, int>>>> res(l, vector<vector<pair<int, int>>>(l));
if (k == 0) {
for (int i = 0; i < l; i++) {
for (int j = 0; j < l; j++) {
res[i][j].emplace_back(i, j);
}
}
return res;
}
// make l x l board from (l + 2) x (l + 2)
// (x, y) <- (nx, ny) such that c[nx] == x and c[ny] == y
auto t = original_pos(k - 1, n);
auto c = move_from(k - 1, n);
for (int x = 0; x < l; x++) {
for (int y = 0; y < l; y++) {
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
if (x == c[x + i] && y == c[y + j]) {
for (auto p : t[x + i][y + j]) {
res[x][y].emplace_back(p);
}
}
}
}
}
}
return res;
}
string process(vector<vector<string>> a, int x, int y, int k, int n) {
auto t = original_pos(k, n);
if (k == n - 1) {
vector<string> s(2 * n + 1, string(2 * n + 1, '0'));
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
for (int id = 0; id < (int) t[i][j].size(); id++) {
s[t[i][j][id].first][t[i][j][id].second] = a[i][j][id];
}
}
}
debug(s);
return count_islands(s);
}
auto c = move_from(k, n);
string res;
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
if (x == c[x + i] && y == c[y + j]) {
res += a[i][j].substr(0, t[x + i][y + j].size());
}
}
}
assert(res.size() <= 100);
res += string(100 - res.size(), '0');
return res;
}
#ifdef tabr
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() {
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);
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");
}
}
}
printf("%lld\n", to_longlong(h[0][0]));
}
}
#endif
