#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,dfn[N],low[N],Sta[N],top,scc[N],tot,cnt,ans,pw[N*N],lk2[N][N],deg[N],rk[N],A,B,C,cnt0;
bool lk[N][N],ins[N],vis[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 F(int x,int y){if(x<y)swap(x,y);return (x-1)*(x-2)/2+y-1;}
void Tarjan(int x)
{
	dfn[x]=low[x]=++tot;
	ins[Sta[++top]=x]=1;
	int pos=-1;
	for(int y=1;y<=n;y++)if(lk[x][y])
	{
		if(!dfn[y])
		{
			vec.push_back({x,y});
			vis[x][y]=1;
			Tarjan(y);
			low[x]=min(low[x],low[y]);
		}
		else if(ins[y]&&dfn[y]<low[x])
		{
			low[x]=dfn[y];
			pos=y;
		}
	}
	if(~pos)vec.push_back({x,pos}),vis[x][pos]=1;
	// printf("%d %d %d\n",x,dfn[x],low[x]),fflush(stdout);
	if(low[x]!=dfn[x])return;
	scp[++cnt].clear();
	while(1)
	{
		int u=Sta[top--];
		ins[u]=0;
		scc[u]=cnt;
		scp[cnt].push_back(u);
		if(u==x)break;
	}
}
void Tarjan2(int x)
{
	dfn[x]=low[x]=++tot;
	ins[Sta[++top]=x]=1;
	if(x==B)
	{
		if(!dfn[A])
		{
			Tarjan2(A);
			low[x]=min(low[x],low[A]);
		}
		else if(ins[A])low[x]=min(low[x],dfn[A]);
	}
	for(int y:scp[C])if(lk[x][y]&&(x!=A||y!=B))
	{
		if(!dfn[y])
		{
			Tarjan2(y);
			low[x]=min(low[x],low[y]);
		}
		else if(ins[y])low[x]=min(low[x],dfn[y]);
	}
	if(low[x]!=dfn[x])return;
	++cnt0;
	while(1)
	{
		int u=Sta[top--];
		ins[u]=0;
		if(u==x)break;
	}
}
void Solve()
{
	vec.clear();
	ans=tot=cnt=0;
	scanf("%d",&n);
	for(int i=1;i<=n;i++)dfn[i]=0;
	for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)vis[i][j]=lk2[i][j]=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;
			}
		}
	}
	// for(int i=1;i<=n;i++,puts(""))for(int j=1;j<=n;j++)printf("%d",lk[i][j]);
	// 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++)if(!dfn[i])Tarjan(i);
	// return;
	for(int i=1;i<=n;i++)dfn[i]=0;
	for(int i=1;i<=cnt;i++)
	{
		C=i;
		for(PII p:vec)if(scc[p.fi]==i&&scc[p.se]==i)
		{
			A=p.fi,B=p.se,cnt0=0;
			for(int x:scp[i])if(!dfn[x])Tarjan2(x);
			// DFS(A);
			// printf("ans:%d %d %d\n",A,B,cnt-1+cnt0);
			(ans+=(ll)pw[F(A,B)]*(cnt-1+cnt0)%Mod)%=Mod;
			for(int x:scp[i])dfn[x]=0;
		}
	}
	for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)
		if(lk[i][j]&&scc[i]!=scc[j])++lk2[scc[i]][scc[j]],++deg[scc[i]];
	for(int i=1;i<=cnt;i++)if(!deg[i])Sta[++top]=i;
	tot=0;
	while(top)
	{
		int x=Sta[top--];
		rk[x]=++tot;
		for(int i=1;i<=cnt;i++)if(lk2[i][x]&&!(deg[i]-=lk2[i][x]))Sta[++top]=i;
	}
	for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)if(lk[i][j])
	{
		int x=scc[i],y=scc[j];
		if(x==y&&!vis[i][j])
		printf("ans:%d %d %d\n",i,j,cnt),
		(ans+=(ll)pw[F(i,j)]*cnt%Mod)%=Mod;
		else if(x!=y)
		{
			if(rk[x]>rk[y])swap(x,y);
			if(rk[x]+1<rk[y]||scp[x].size()>1||scp[y].size()>1)(ans+=(ll)pw[F(i,j)]*(cnt-rk[y]+rk[x])%Mod)%=Mod;
			else (ans+=(ll)pw[F(i,j)]*cnt%Mod)%=Mod;
		}
	}
	printf("%d\n",ans);
}
int main()
{
    #ifndef ONLINE_JUDGE
    freopen(".in","r",stdin);
    freopen(".out","w",stdout);
    #endif

	pw[0]=1;
	for(int i=1;i<N*N;i++)pw[i]=2*pw[i-1]%Mod;
	scanf("%d",&Q);
	while(Q--)Solve();

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