#include<bits/stdc++.h>
#define ll long long
#define Int __int128
#define ld double
#define fi first
#define se second
#define PII pair<int,int>
#define PLI pair<ll,int>
#define PIL pair<int,ll>
#define PLL pair<ll,ll>
#define PLPII pair<ll,PII>
#define Bit bitset<M>
using namespace std;
const int N=5005,Mod=1e9+7;
int Q,n,d[N],d1[N],s[N],c1[N],c2[N],c3[N],ed[N],ans;
bool lk[N][N];
char a[N];
vector<PII>vec;
vector<int>scp[N];
int ID(char x){return x>='0'&&x<='9'?x-'0':x-'A'+10;}
int G(int x){return x*(x-1)/2;}
void Solve()
{
	ans=0;
	scanf("%d",&n);
	for(int i=1;i<=n;i++)d[i]=0;
	for(int i=2;i<=n;i++)
	{
		scanf("%s",a);
		for(int j=0;j<(i+2)/4;j++)
		{
			for(int k=0;k<4;k++)if(j*4+k+1<i)
			{
				int x=ID(a[j])>>k&1;
				lk[i][j*4+k+1]=x,lk[j*4+k+1][i]=!x;
				d[i]+=x,d[j*4+k+1]+=!x;
			}
		}
	}
	// for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)if(lk[i][j])printf("%d %d\n",i,j);
	for(int i=1;i<=n;i++)s[i]=d[i];
	sort(s+1,s+n+1);
	for(int i=1;i<=n;i++)ed[s[i]]=i;
	for(int i=1;i<=n;i++)if(!ed[i])ed[i]=ed[i-1];
	for(int i=1;i<=n;i++)
	{
		s[i]+=s[i-1];
		c1[i]=c1[i-1]+(s[i]==G(i));
		c2[i]=c2[i-1]+(s[i]-1==G(i));
		c3[i]=c3[i-1]+(s[i]+1==G(i));
	}
	// printf("?%d\n",c1[n]);
	// for(int i=1;i<=n;i++)printf("%d ",s[i]);puts("");
	// for(int i=1;i<=n;i++)printf("%d ",G(i));puts("");
	for(int i=n;i;i--)for(int j=i-1;j;j--)
	{
		int x=i,y=j,sum=c1[n];
		if(lk[x][y])swap(x,y);
		if(d[x]>=d[y])sum+=(c2[ed[d[x]]-1]-c2[ed[d[y]-1]])-(c1[ed[d[x]]-1]-c1[ed[d[y]-1]]);
		if(d[x]+1<d[y])sum+=(c3[ed[d[y]-1]]-c3[ed[d[x]]-1])-(c1[ed[d[y]-1]]-c1[ed[d[x]]-1]);
		// printf("%d %d %d %d %d %d %d\n",x,y,d[x],d[y],ed[d[x]],ed[d[y]],sum);
		ans=(ans*2+sum)%Mod;
	}
	printf("%d\n",ans);
}
int main()
{
    #ifndef ONLINE_JUDGE
    freopen(".in","r",stdin);
    freopen(".out","w",stdout);
    #endif

	scanf("%d",&Q);
	while(Q--)Solve();

	fprintf(stderr,"%.15lf\n",(ld)clock()/CLOCKS_PER_SEC);
}