#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 j=1;j<=i-1;j++)
		// {
			// if(f[i][j]==1) printf("%d -> %d\n",i,j);
			// else printf("%d -> %d\n",j,i);
		// }
	}
	for(int i=1;i<=n;i++) a[i]=0;
	for(int i=1;i<=n;i++)
	{
		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=1;i<=n;i++)
	{
		for(int j=1;j<=i-1;j++)
		{
			int pre;
			if(abs(a[i]-a[j])==1) pre=sm0[n];
			else
			{
				int l,r; // l:-1  r:+1
				if(f[i][j]==1) l=lb[pos[i]],r=rb[pos[j]];
				else r=rb[pos[i]],l=lb[pos[j]];
				if(l<r)
				{
					r--;
					// printf("- [%d %d]\n",l,r);
					pre=sm0[n]-(sm0[r]-sm0[l-1])+(sm1[r]-sm1[l-1]);
				}
				else
				{
					swap(l,r);
					r--;
					// printf("+ [%d %d]\n",l,r);
					pre=sm0[n]-(sm0[r]-sm0[l-1])+(sm2[r]-sm2[l-1]);
				}
			}
			// printf("%d %d %d\n",j,i,pre);
			add(ans,1ll*pre*pw2[(i-2)*(i-1)/2+j-1]%p);
		}
	}
	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;
}