// 
/*
https://www.cnblogs.com/xulongkai/p/18007142
*/
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=5005,mod=1e9+7;
int T;
int n;
bool g[N][N];
int d[N];
int get(char ch){
	if('0'<=ch&&ch<='9'){
		return ch-'0';
	}
	return ch-'A'+10;
}
int s[N],siz[N];
int sum[N][2];
int ans;
void solve(){
	scanf("%lld",&n);
	for(int i=1;i<=n;i++){
		d[i]=siz[i]=0;
	}	
	for(int i=2;i<=n;i++){
		string s;
		cin>>s;
		for(int j=0;j<(i+2)/4;j++){
			for(int k=0;k<4;k++){
				if(j*4+k+1<i){
					int x=get(s[j])>>k&1;
					g[i][j*4+k+1]=x,g[j*4+k+1][i]=!x;
					d[i]+=x,d[j*4+k+1]+=!x;
				}
			}
		}
	}
	for(int i=1;i<=n;i++){
		s[i]=d[i];
		siz[d[i]]++;
	}
	for(int i=1;i<=n;i++){
		siz[i]+=siz[i-1];
	}
	sort(s+1,s+n+1);
	for(int i=1;i<=n;i++){
		s[i]+=s[i-1];
		sum[i][0]=sum[i-1][0]+(s[i]==(i*(i-1)/2));//交换前 
		sum[i][1]=sum[i-1][1]+(s[i]==(i*(i-1)/2+1));//交换后	
	}
	ans=0;
	for(int i=n;i>=1;i--){
		for(int j=i-1;j>=1;j--){
			int x=i,y=j,res=sum[n][0];
			if(g[x][y]){
				swap(x,y);
			}
			if(d[x]>=d[y]){//交换前在同一个强连通分量
				res+=(sum[siz[d[x]]-1][1]-sum[siz[d[y]-1]][1]);
			}
			if(d[x]+1<d[y]){//交换后在同一个强连通分量
				res-=(sum[siz[d[y]-1]][0]-sum[siz[d[x]]-1][0]);
			}
			ans=(ans*2+res)%mod;
		}	
	}
	printf("%lld\n",ans);
}
signed main(){
	scanf("%lld",&T);
	while(T--){
		solve();
	}
	return 0;
}
/*
2
3
0
2
6
1
3
7
F
F1
*/