#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
int pow2[25000010];
int n;
bool e[5010][5010];
int deg[5010];
pair<int,int> px[5010];
int tot,r[5010];
int ans[5010][5010];
int ddeg[5010];
void get_hamilton(vector<int> &now)
{
	if(now.size()==1) return;
	int x=now[0];
	for(int i:now) ddeg[i]-=e[i][x];
	int ttot=0; pair<int,int> ppx[5010];
	for(int i:now) if(i!=x) ppx[++ttot]={ddeg[i],i};
	sort(ppx+1,ppx+ttot+1,greater<pair<int,int>>());
	int sum=0,lst=0;
	int cnt=0; vector<int> gt[5010];
	for(int i=1; i<=ttot; ++i)
	{
		sum+=ppx[i].first;
		if(sum==i*(i-1)/2+i*(ttot-i))
		{
			++cnt;
			for(int j=lst+1; j<=i; ++j) gt[cnt].push_back(ppx[j].second),ddeg[ppx[j].second]-=ttot-i;
			lst=i;
			get_hamilton(gt[cnt]);
		}
	}
	if(cnt==1)
	{
		vector<int> ans;
		for(int i=0; i<gt[1].size(); ++i)
		{
			if(e[gt[1][i]][x] && e[x][gt[1][(i+1)%gt[1].size()]])
			{
				for(int j=0; j<=i; ++j) ans.push_back(gt[1][j]);
				ans.push_back(x);
				for(int j=i+1; j<gt[1].size(); ++j) ans.push_back(gt[1][j]);
				break;
			}
		}
		now=ans;
	}
	else
	{
		vector<int> ans;
		for(int i=1; i<=cnt; ++i)
		{
			if(i==1)
			{
				int wz=0;
				while(!e[x][gt[i][wz]]) ++wz;
				for(int j=wz; j<gt[i].size(); ++j) ans.push_back(gt[i][j]);
				for(int j=0; j<wz; ++j) ans.push_back(gt[i][j]);
			}
			else if(i==cnt)
			{
				int wz=0;
				while(!e[gt[i][wz]][x]) ++wz;
				for(int j=wz+1; j<gt[i].size(); ++j) ans.push_back(gt[i][j]);
				for(int j=0; j<=wz; ++j) ans.push_back(gt[i][j]);
			}
			else
			{
				for(int j:gt[i]) ans.push_back(j);
			}
		}
		ans.push_back(x);
		now=ans;
	}
}
int cnt[5010];
int get_ans(int x,int y)
{
	if(e[x][y]) --deg[x],++deg[y];
	else --deg[y],++deg[x];
	memset(cnt,0,(n+5)*4);
	for(int i=1; i<=n; ++i) ++cnt[deg[i]];
	int wz=0,sum=0,ans=0;
	for(int i=n; i>=0; --i)
	{
		for(int j=1; j<=cnt[i]; ++j)
		{
			++wz,sum+=i;
			if(sum==wz*(wz-1)/2+wz*(n-wz)) ++ans;
		}
	}
	if(e[x][y]) ++deg[x],--deg[y];
	else ++deg[y],--deg[x];
	return ans;
}
int main()
{
	pow2[0]=1;
	for(int i=1; i<=2.5e7; ++i) pow2[i]=pow2[i-1]*2%mod;
	ios::sync_with_stdio(false),cin.tie(0);
	int t; cin>>t; while(t--)
	{
		cin>>n;
		for(int i=1; i<=n; ++i) for(int j=1; j<=n; ++j) e[i][j]=0;
		memset(deg,0,(n+5)*4);
		for(int i=2; i<=n; ++i)
		{
			string s; cin>>s;
			for(int j=1; j<i; ++j)
			{
				int now=s[(j-1)/4];
				if('0'<=now && now<='9') now-='0';
				else now=10+now-'A';
				if(now>>((j-1)%4)&1) e[i][j]=1,++deg[i];
				else e[j][i]=1,++deg[j];
			}
		}
		for(int i=1; i<=n; ++i) px[i]={deg[i],i};
		sort(px+1,px+n+1,greater<pair<int,int>>());
		tot=0;
		int sum=0;
		for(int i=1; i<=n; ++i)
		{
			sum+=px[i].first;
			if(sum==i*(i-1)/2+i*(n-i)) r[++tot]=i;
		}
		for(int i=1; i<=tot; ++i)
		{
			for(int j=i+1; j<=tot; ++j)
			{
				int aans;
				if(i+1==j && r[i]-r[i-1]==1 && r[j]-r[j-1]==1) aans=tot;
				else aans=tot-(j-i);
				for(int k=r[i-1]+1; k<=r[i]; ++k)
				{
					for(int l=r[j-1]+1; l<=r[j]; ++l) ans[px[k].second][px[l].second]=ans[px[l].second][px[k].second]=aans;
				}
			}
		}
		for(int i=1; i<=tot; ++i)
		{
			vector<int> now;
			for(int j=r[i-1]+1; j<=r[i]; ++j) now.push_back(px[i].second),ddeg[px[j].second]=0;
			for(int j:now)
			{
				for(int k:now) ddeg[j]+=e[j][k];
			}
			get_hamilton(now);
			for(int j=r[i-1]+1; j<=r[i]; ++j)
			{
				for(int k=r[i-1]+1; k<=r[i]; ++k) ans[px[j].second][px[k].second]=tot;
			}
			for(int j=0; j<now.size(); ++j)
			{
				int x=px[j].second,y=px[(j+1)%now.size()].second;
				ans[x][y]=ans[y][x]=get_ans(x,y);
			}
		}
		int aans=0;
		for(int i=1; i<=n; ++i)
		{
			for(int j=1; j<i; ++j) aans=(aans+1ll*pow2[(i-2)*(i-1)/2+j-1]*ans[i][j])%mod;
		}
		cout<<aans<<'\n';
	}
	return 0;
}