#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define op(x) ((x&1)?x+1:x-1)
#define odd(x) (x&1)
#define even(x) (!odd(x))
#define lc(x) (x<<1)
#define rc(x) (lc(x)|1)
#define lowbit(x) (x&-x)
#define mp(x,y) make_pair(x,y)
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
using namespace std;
const int MAXN=5010,mod=1e9+7;
const int MAXM=MAXN*MAXN,LIM=2.5e7;
typedef vector<int> vec;

void add(int& x,int y){x=(x+y)%mod;}

int n,pw[MAXM],ans;
int G[MAXN][MAXN];

int C(int n){return n*(n-1)/2;}
int deg[MAXN],rk[MAXN];

int pre[MAXN],suf[MAXN],sum[MAXN],ed[MAXN];

void ok(int i,int j,int val){
	if(i<j)swap(i,j);
	int e=(i-1)*(i-2)/2 + (j-1);

	add(ans,1ll*val*pw[e]%mod);
}

void solve(int u){
	deg[u]--;

	iota(rk+1,rk+1+n,1);
	sort(rk+1,rk+1+n,[&](int x,int y){return deg[x] < deg[y];});

	rep(i,1,n){
		sum[i]=sum[i-1] + deg[rk[i]];
		pre[i]=pre[i-1] + (sum[i]==C(i));
	}

	per(i,n,1)suf[i]=suf[i+1] + (sum[i]==C(i)-1);

	int cur=0;
	rep(i,0,n){
		while(cur+1 <= n && deg[rk[cur+1]]==i)cur++;
		ed[i]=cur;
	}

	rep(v,1,n)if(G[u][v]){
		int val=deg[v];
		ok(u,v,pre[ed[val]-1] + suf[ed[val]]);
	}


	deg[u]++;
}
int main(){
	ios::sync_with_stdio(false);

	pw[0]=1;
	rep(i,1,LIM)pw[i]=pw[i-1]*2%mod;

	int T;cin>>T;

	while(T--){

	ans=0;

	cin>>n;
	
	rep(i,1,n-1){
		string s;
		cin>>s;
		int len=s.length();
		s=" "+s;
		rep(j,1,len){
			char ch=s[j];
			int num;
			if(isdigit(ch))num=ch-'0';
			else num=10 + (ch-'A');
			rep(k,0,3){

				if(num>>k&1){
					G[i+1][4*j+k-3]=1;
				}else if(i+1 > 4*j+k-3){
					G[4*j+k-3][i+1]=1;
				}
			}
		}
	}

	rep(u,1,n)deg[u]=0;

	rep(u,1,n)rep(v,1,n)if(G[u][v])deg[u]++;

	rep(u,1,n)solve(u);

	cout<<ans<<"\n";

	rep(i,1,n)rep(j,1,n)G[i][j]=0;
	}

    return 0;
}