CodeChef submission 64251 (C++ 4.0.0-8) plaintext list. Status: AC, problem F3, contest AUG09. By gmark (Mark Greve), 2009-08-04 18:34:36.
// Curry Stained Napkin
// Source: CodeChef August 2009 Algorithm Challenge
// CodeChef ID: F3
// Date: 03-08-2009
// Author: Mark Greve
 
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
using namespace std;
 
const int MOD=21945;
typedef long long LL;
int N;
 
int power2(int n) {
	if (n==0) return 1;
	int hf = power2(n/2);
	hf = (hf*hf)%MOD;
	return n%2==0 ? hf : ((hf*2)%MOD);
}
 
vector<string> reflect_hor(vector<string> v) {
	for (int i=0;i<v.size();++i) {
		for (int j=0;j<v[i].size()-1-j;++j) {
			swap(v[i][j], v[i][v[i].size()-1-j]);
		}
	}
	return v;
}
vector<string> reflect_ver(vector<string> v) {
	for (int j=0;j<v[0].size();++j) {
		for (int i=0;i<v.size()-1-i;++i) {
			swap(v[i][j], v[v.size()-1-i][j]);
		}
	}
	return v;
}
vector<string> reflect_both(vector<string> v) {
	v = reflect_hor(v);
	v = reflect_ver(v);
	return v;
}
 
vector<string> append_ver(vector<string> a, vector<string> b) {
	a.insert(a.end(), b.begin(),b.end());
	return a;
}
 
vector<string> append_hor(vector<string> a, vector<string> b) {
	for (int i=0;i<min(a.size(),b.size());++i) a[i] += b[i];
	return a;
}
 
int regions(const vector<string>& v) {
	vector<vector<bool> > vis(v.size());
	for (int i=0;i<v.size();++i) vis[i] = vector<bool>(v[i].size(),0);
 
	int ans = 0;
	for (int i=0;i<v.size();++i) {
		for (int j=0;j<v[i].size();++j) if (!vis[i][j] && v[i][j]=='1') {
			++ans;
			vis[i][j] = 1;
			queue<int> q;
			q.push(i), q.push(j);
			while (!q.empty()) {
				int x = q.front(); q.pop();
				int y = q.front(); q.pop();
				const int dx[]={0,0,1,-1};
				const int dy[]={-1,1,0,0};
				for (int k=0;k<4;++k) {
					int nx = x + dx[k];
					int ny = y + dy[k];
					if (0 <= nx && nx < v.size() && 0 <= ny && ny < v[nx].size()) {
						if (!vis[nx][ny] && v[nx][ny]=='1') {
							vis[nx][ny] = 1;
							q.push(nx), q.push(ny);
						}
					}
				}
			}
		}
	}
	return ans;
}
 
void show(const vector<string>& v) {
	cout << "------------" << endl;
	for (int i=0;i<v.size();++i) {
		cout << v[i] << endl;
	}
	cout << "REGIONS " << regions(v) << endl;
	cout << "------------" << endl;
}
 
int solve(const vector<string>& r) {
	LL tt = power2(N-4)%MOD;
 
	LL tot = regions(r);
	//cout << "\tTOT " << tot << endl;
	vector<string> h = append_hor(r,r);
	//show(h);
	LL addleft = regions(h) - tot;
	assert(addleft>=0);
	//cout << "\tADDLEFT " << addleft << endl;
 
	vector<string> v = append_ver(r,r);
	LL adddown = regions(v) - tot;
	assert(adddown>=0);
	//cout << "\tADDDOWN " << addleft << endl;
 
	vector<string> q = append_ver(h,r);
	vector<string> z = append_ver(h,h);
	LL add = regions(z) - regions(q);
	assert(add>=0);
	//cout << "\tADD " << addleft << endl;
 
	LL ans = tot;
	ans = (ans + (tt-1)*addleft)%MOD;
	ans = (ans + (tt-1)*adddown)%MOD;
	ans = (ans + (tt-1)*(tt-1)*add)%MOD;
	return ans;
}
 
vector<string> build(const vector<string>& p) {
	vector<string> h = reflect_hor(p);
	vector<string> v = reflect_ver(p);
	vector<string> b = reflect_both(p);
 
	vector<string> x = append_hor(p,h);
	vector<string> y = append_hor(v,b);
	vector<string> r = append_ver(x,y);
	return r;
}
 
int go(const vector<string>& p) {
	if (N==3) return regions(p)%MOD; // total number of regions
	vector<string> r = build(p);	
	if (N==4) return regions(r)%MOD;
	return solve(r);
}
 
int bf(vector<string> p) {
	int n = N;
	if (n==3) return regions(p)%MOD;
	p = build(p);
	while (n>4) {
		vector<string> z = append_hor(p,p);
		z = append_ver(z,z);
		p = z;
		--n;
	}
	//cerr << "FINAL " << endl;
	//assert(p.size() == p[0].size());
	//show(p);
	return regions(p)%MOD;
}
 
 
 
 
 
int naivesolver(vector<string> p, int N) {
	while (N>3) {	
		p = append_hor(p, reflect_hor(p));
		p = append_ver(p, reflect_ver(p));
		--N;
	}
	show(p);
	return regions(p)%MOD;
}
 
int fastsolve(const vector<string>& v) {
	//cerr << "N " << N << endl;
	int mine = go(v);
	/*
	if (N<=9) {
		//cerr << "TEST " << endl;
		int naive = bf(v);
		if (naive!=mine) {
			cerr << "FAILS TEST 1 " << naive << " vs mine ==> " << mine << endl;
			assert(0);
		}
		int naive2 = naivesolver(v,N);
		if (naive2!=mine) {
			cerr << "FAILS TEST 2 " << naive2 << " vs mine ==> " << mine << endl;
			assert(0);
		}
	}
	else {
	//	cerr  << "NO TEST " << endl;
	}
	*/
 
	return mine;
}
 
 
int main() {
	int NCASES;
	cin >> NCASES;
	for (int z=1;z<=NCASES;++z) {
		//cerr << "CASE " << z << endl;
		cin >> N;
		vector<string> v;
		for (int i=0;i<8;++i) {
			string s;
			cin >> s;
			v.push_back(s);
		}
		//cerr << "INPUT " << endl;
		//show(v);
		int ans = fastsolve(v);
		ans = ((ans%MOD)+MOD)%MOD;
		printf("%d\n", go(v));
	}
}