#include <iostream>
#include <algorithm>
#include <cstdio>

using namespace std;

const int S=5005,p=1000000007;

int pw2[S*S];
int n;
char tmp[S];
int f[S][S],a[S];
int id[S],pos[S],lb[S],rb[S];
int b[S],sm0[S],sm1[S],sm2[S];

inline void add(int &x,int y)
{
	x+=y;
	if(x>=p) x-=p;
}

inline void slove()
{
	scanf("%d",&n);
	for(int i=2;i<=n;i++)
	{
		scanf("%s",tmp+1);
		for(int j=1;j<=(i-1)/4+!!((i-1)%4);j++)
		{
			if(tmp[j]>='A'&&tmp[j]<='F') tmp[j]=tmp[j]-'A'+10;
			else tmp[j]-='0';
			f[i][j*4-3+0]=tmp[j]&1,tmp[j]>>=1;
			f[i][j*4-3+1]=tmp[j]&1,tmp[j]>>=1;
			f[i][j*4-3+2]=tmp[j]&1,tmp[j]>>=1;
			f[i][j*4-3+3]=tmp[j]&1,tmp[j]>>=1;
		}
	}
	for(int i=1;i<=n;i++)
	{
		a[i]=0;
		for(int j=1;j<=i-1;j++) a[i]+=f[i][j];
		for(int j=i+1;j<=n;j++) a[i]+=1-f[j][i];
	}
	for(int i=1;i<=n;i++) id[i]=i;
	sort(id+1,id+n+1,[&](int x,int y){return a[x]<a[y];});
	for(int i=1;i<=n;i++) pos[id[i]]=i;
	for(int i=1;i<=n;i++)
	{
		if(i>1&&a[id[i]]==a[id[i-1]]) lb[i]=lb[i-1];
		else lb[i]=i;
	}
	for(int i=n;i>=1;i--)
	{
		if(i<n&&a[id[i]]==a[id[i+1]]) rb[i]=rb[i+1];
		else rb[i]=i;
	}
	for(int i=1;i<=n;i++) b[i]=b[i-1]+a[id[i]];
	for(int i=1;i<=n;i++) b[i]-=i*(i-1)/2;
	for(int i=1;i<=n;i++)
	{
		sm0[i]=sm0[i-1]+(b[i]==0);
		sm1[i]=sm1[i-1]+(b[i]==1);
		sm2[i]=sm2[i-1]+(b[i]==-1);
	}
	// for(int i=1;i<=n;i++) printf("%d %d %d\n",id[i],a[id[i]],b[i]);
	int ans=0;
	for (int i = n, tmp, l, r;i >= 2;i --){
		for (int j = i - 1;j >= 1;j --){
			if (f[i][j]) swap(i, j);
			tmp = sm0[n], l = rb[pos[i]], r = lb[pos[j]];
			if (a[l] + 1 == a[r]) goto Calc; 
			if (l < r) tmp += sm1[r - 1] - sm1[l - 1] - sm0[r - 1] + sm0[l - 1];
			else tmp += sm2[l - 1] - sm2[r - 1] - sm0[l - 1] + sm0[r - 1];
			Calc: ans = (ans * 2ll + tmp) % p;
			if (f[j][i]) swap(i, j);
		}
	}
	printf("%d\n",ans);
}

int main()
{
	pw2[0]=1;
	for(int i=1;i<=S*S-3;i++) pw2[i]=2ll*pw2[i-1]%p;
	int T;
	scanf("%d",&T);
	while(T-->0) slove();
	return 0;
}