#include <bits/stdc++.h>
#define rep(i,j,k) for(int i=(j);i<=(k);i++)
#define per(i,j,k) for(int i=(j);i>=(k);i--)
#define uint unsigned int
#define ll long long
#define ull unsigned long long
#define db double
#define ldb long double
#define pii pair<int,int>
#define pll pair<ll,ll>
#define mkp make_pair
#define eb emplace_back
#define SZ(S) (int)S.size()
//#define mod 998244353
#define mod 1000000007
#define inf 0x3f3f3f3f
#define linf 0x3f3f3f3f3f3f3f3f
using namespace std;

template <class T>
void chkmax(T &x,T y){
	if(x < y) x = y;
}

template <class T>
void chkmin(T &x,T y){
	if(x > y) x = y;
}

inline int popcnt(int x){
	return __builtin_popcount(x);
}

inline int ctz(int x){
	return __builtin_ctz(x);
}


ll power(ll p,int k = mod - 2){
	ll ans = 1;
	while(k){
		if(k % 2 == 1) ans = ans * p % mod;
		p = p * p % mod;
		k /= 2;	
	}
	return ans;
}
int T,n;
bitset <5005> G[5005];
int deg[5005];
char str[5005];

int getval(char ch){
	if('0' <= ch && ch <= '9') return ch - '0';
	return ch - 'A' + 10;
}

int k;
int p[5005];
ll P[2][5005];
ll getval(int u,int v){
	if(u < v) swap(u,v);
	return P[1][u] * P[0][v] % mod;
}

void rev(int u,int v){
	if(G[u].test(v)){
		G[u].reset(v);
		G[v].set(u);
		return;	
	}
	//v -> u
	G[u].set(v);
	G[v].reset(u);
}

int calc(){
	k = 0;
	p[++k] = 1;
	rep(i,2,n){
		if(!G[p[1]].test(i)){
			per(j,k + 1,2) p[j] = p[j - 1];
			p[1] = i;
			k++;
			continue;
		}
		if(G[p[k]].test(i)){
			p[++k] = i;
			continue;
		}
		rep(j,1,k - 1){
			if(G[p[j]].test(i) && !G[p[j + 1]].test(i)){
				//插在 j+1 的位置
				per(s,k + 1,j + 2) p[s] = p[s - 1]; 
				p[j + 1] = i;
				++k;
				break;
			}
		}
	}	
	fill(deg,deg + n + 1,0);
	rep(i,1,n){
		rep(j,i + 1,n){
			if(G[i].test(j)) deg[j]++;
			else deg[i]++;
		}
	}
//	rep(i,1,n) printf("%d ",p[i]);
//	printf("\n");

	int ans = 0,sum = 0;
	rep(i,1,n){
		sum += deg[p[i]];
		if(sum == i * (i - 1) / 2) ans++;
	}
	return ans;
}

void solve(){
	scanf("%d",&n);
	rep(i,1,n){
		rep(j,1,n) G[i].reset(j);
	}
	rep(i,1,n) P[1][i] = power(2,(i - 2) * (i - 1) / 2);
	rep(i,1,n) P[0][i] = power(2,i - 1);
	rep(i,2,n){
		scanf("%s",str + 1);
		rep(j,1,(i + 3) / 4){
			int v = getval(str[j]);
			if((v & 1) && 4 * j - 3 < i) G[i].set(4 * j - 3);
			if((v & 2) && 4 * j - 2 < i) G[i].set(4 * j - 2);
			if((v & 4) && 4 * j - 1 < i) G[i].set(4 * j - 1);
			if((v & 8) && 4 * j < i) G[i].set(4 * j);
		}
	}
	rep(i,1,n){
		rep(j,1,i - 1){
			if(!G[i].test(j)) G[j].set(i);
		}
	}
/*	rep(u,1,n){
		rep(v,1,n) printf("%d ",G[u].test(v));
		printf("\n");
	}*/

	ll ans = 0;
	rep(u,1,n){
		rep(v,u + 1,n){
			rev(u,v);
//			printf("rev edge %d->%d\n",u,v);
			ans += P[1][v] * P[0][u] % mod * calc();
			rev(u,v);
		}
		ans %= mod;
	}
	printf("%lld\n",ans);
}

int main(){
//	freopen("test.in","r",stdin);
	scanf("%d",&T);
	while(T--) solve();
	return 0;
}