#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
int c[5005][5005],du[5005];
bool cmp(int x,int y){return du[x]<du[y];}
vector<int>fr[5005],to[5005];
void add(int aa,int bb)
{
	//cout<<aa<<"->"<<bb<<endl;
	fr[bb].push_back(aa);
	to[aa].push_back(bb);
	du[aa]++;
}
void init(int n)
{
	for(int i=1;i<=n;i++)
	for(int j=1;j<=n;j++) c[i][j]=0;
	for(int i=1;i<=n;i++) du[i]=0,fr[i].clear(),to[i].clear();
}
int vis[5005];
vector<int>solve(vector<int> vec)
{
	if(vec.size()==1) return vec;
	//for(int i=0;i<vec.size();i++)
	//cout<<vec[i]<<" ";puts("");
	vector<int>prf;int x=vec.back();vec.pop_back();
	for(int i=0;i<vec.size();i++) vis[vec[i]]=1;
	for(int i=0;i<fr[x].size();i++)
	if(vis[fr[x][i]]) du[fr[x][i]]--;
	for(int i=0;i<vec.size();i++) vis[vec[i]]=0;
	//删掉一个点在其它点的导出子图求强连通分量 
	sort(vec.begin(),vec.end(),cmp);
	long long sum=0;int las=-1;
	for(int i=0;i<vec.size();i++)
	{
		int u=vec[i];sum+=du[u]-las-1;
		//cout<<u<<":"<<du[u]<<endl;
		if(sum==(i-las)*(i-las-1)/2)
		{
			//cout<<u<<endl;
			vector<int>now,tmp;
			for(int j=las+1;j<=i;j++)
			du[vec[j]]-=las+1,now.push_back(vec[j]);
			tmp=solve(now);las=i;sum=0;
			for(int j=tmp.size()-1;j>=0;j--)
			prf.push_back(tmp[j]);
			//cout<<u<<"is fine"<<endl;
		}
	}
	for(int i=0;i<prf.size()/2;i++) swap(prf[i],prf[prf.size()-1-i]);
	//for(int i=0;i<prf.size();i++) cout<<prf[i]<<" ";puts("");
	prf.push_back(x);
	return prf;
}
char s[5005];
int md[3000005],b[5005],M=3000000,ans,tot;
int tv[10005],val[10005],v0[10005],pos[5005],si[5005];
int gval(int i,int j){if(i<j)swap(i,j);return md[(i-2)*(i-1)/2+j-1];}
void getans(vector<int>vec,int ps)
{
	vector<int>prf=solve(vec);int m=vec.size();
	//for(int i=0;i<m;i++) cout<<prf[i]<<" ";puts("");
	//吾有三贡献：哈密顿路径上、哈密顿路径外、到出度更小的连通块 
	for(int i=0;i<m;i++) pos[prf[i]]=i;
	for(int i=0;i<m*2;i++) val[i]=0;
	for(int i=0;i<m;i++)
	{
		int u=prf[i];
		for(int j=0;j<to[u].size();j++)
		{
			int v=pos[to[u][j]];
			if(b[v]!=ps) continue;
			if(v==(i+1)%m) continue;
			//cout<<v<<"~"<<i<<endl;
			if(v<i) val[v]++,val[i]--;
		}
	}
	if(m!=1)
	{
		tv[0]=val[0];v0[0]=(tv[0]==0);
		for(int i=1;i<m;i++) tv[i]=tv[i-1]+val[i];
		for(int i=1;i<m;i++) v0[i]=v0[i-1]+(tv[i]==0);
		ans=(ans+1ll*gval(prf[m-1],prf[0])*(tot+v0[m-1])%mod)%mod;
		//for(int i=0;i<m;i++) cout<<tv[i]<<" ";puts(""); 
		//cout<<prf[m-1]<<" "<<prf[0]<<":"<<tot+v0[m-2]<<endl;
	}
	for(int i=0;i<m-1;i++)
	{
		int u=prf[i];
		for(int j=0;j<to[u].size();j++)
		{
			int v=pos[to[u][j]];
			if(b[v]!=ps) continue;
			if(v==(i+1)%m) continue;
			if(v>i) val[v]++,val[i+m]--;
			else val[v+m]++,val[i+m]--;
		}
		for(int j=0;j<fr[u].size();j++)
		{
			int v=pos[fr[u][j]];
			if(b[v]!=ps) continue;
			if(i==(v+1)%m) continue;
			if(v>i) val[i]--,val[v]++;
			else val[i]--,val[v+m]++;
		}//这里理论上从i位开始前缀和就是对的 
		tv[0]=val[0];v0[0]=(tv[0]==0);
		for(int j=1;j<=m+i;j++) tv[j]=tv[j-1]+val[j];
		for(int j=1;j<=m+i;j++) v0[j]=v0[j-1]+(tv[j]==0);
		//for(int j=0;j<=m+i;j++) cout<<tv[j]<<" ";puts("");
		ans=(ans+1ll*gval(prf[i],prf[i+1])*(tot+v0[m+i-1]-v0[i])%mod)%mod;
		//cout<<prf[i]<<" "<<prf[i+1]<<":"<<tot+v0[m+i-1]-v0[i]<<endl;
	}
	for(int ii=0;ii<m;ii++)
	{
		int i=vec[ii];//cout<<i<<endl;
		for(int j=0;j<to[i].size();j++)
		{
			int va=gval(to[i][j],i);
			//cout<<to[i][j]<<" "<<i<<":"<<va<<endl;
			if(b[to[i][j]]==ps){
				if(pos[to[i][j]]!=(pos[i]+1)%m)
				ans=(ans+1ll*va*tot%mod)%mod;
			}
			else
			{
				if(b[to[i][j]]==ps-1&&si[ps]==1&&si[ps-1]==1)
				ans=(ans+1ll*va*tot%mod)%mod;
				//仍然是链,形态会变成 1->v->u->v+1->n 
				else ans=(ans+1ll*va*(tot-(ps-b[to[i][j]]))%mod)%mod;
			}
		}
	}
}
int main()
{
	int tim;cin>>tim;md[0]=1;
	for(int i=1;i<=M;i++) md[i]=2ll*md[i-1]%mod;
	while(tim--)
	{
		int n;cin>>n;ans=tot=0;init(n);
		for(int i=2;i<=n;i++)
		{
			scanf("%s",s+1);
			for(int j=1;j<=(i+3)/4;j++)
			{
				int val=(s[j]<='9'?s[j]-'0':s[j]-'A'+10);
				for(int k=1;k<=4;k++)
				c[i][(j-1)*4+k]=(val>>k-1)&1;
			}
			for(int j=1;j<i;j++)
			if(c[i][j]) add(i,j);
			else add(j,i);
		}
		vector<int>vec;
		for(int i=1;i<=n;i++) vec.push_back(i);
		sort(vec.begin(),vec.end(),cmp);
		long long sum=0;int las=-1;
		for(int i=0;i<vec.size();i++)
		{
			int uu=vec[i];sum+=du[uu]-las-1;
			//cout<<u<<":"<<du[u]<<endl;
			if(sum==(i-las)*(i-las-1)/2)
			{
				si[++tot]=0;
				for(int j=las+1;j<=i;j++)
				b[vec[j]]=tot,si[tot]++;
				las=i;sum=0;
			}
		}
		sum=0;las=-1;int tmp=0;
		for(int i=0;i<vec.size();i++)
		{
			int uu=vec[i];sum+=du[uu]-las-1;
			//cout<<u<<":"<<du[u]<<endl;
			if(sum==(i-las)*(i-las-1)/2)
			{
				vector<int>now;
				for(int j=las+1;j<=i;j++)
				du[vec[j]]-=las+1,now.push_back(vec[j]);
				getans(now,++tmp);las=i;sum=0;
			}
		}
		printf("%d\n",ans);
	}
	return 0;
}