#include <bits/stdc++.h>
#define N 5005
#define M 13000005
using namespace std;
const int mod=1e9+7;
int power(int x,int y) {
	int ans=1;
	while(y) {
		if(y&1) ans=1ll*ans*x%mod;
		x=1ll*x*x%mod,y>>=1;
	}
	return ans;
}
int T,n,ans,tot,first[N],nxt[M],ver[M],pw2[N],pw[N];
void add(int s,int e) {
	nxt[++tot]=first[s];
	first[s]=tot;
	ver[tot]=e;
}
bool vis[N];
int dfn[N],totd,low[N],s[N],top,totb,blo[N];
vector<int> b[N];
void tarjan(int now,int fa) {
	dfn[now]=low[now]=++totd;
	vis[now]=1,s[++top]=now;
	for(int i=first[now];i;i=nxt[i]) {
		int v=ver[i];
		if(v==fa) continue;
		if(!dfn[v]) {
			tarjan(v,now);
			low[now]=min(low[now],low[v]);
		} else if(vis[v]) {
			low[now]=min(low[now],dfn[v]);
		}
	}
	if(low[now]>=dfn[now]) {
		blo[now]=++totb;
		b[totb].push_back(now);
		while(top&&s[top]!=now) {
			b[totb].push_back(s[top]);
			vis[s[top]]=0;
			blo[s[top--]]=totb;
		}
		if(top) vis[s[top--]]=0;
	}
}
int ind[N],oud[N],deg[N][N],wou[N],win[N];
vector<int> head[N],hb[N],hbin[N];
void build() {
	for(int i=1;i<=n;++i) for(int j=first[i];j;j=nxt[j]) {
		if(blo[i]==blo[ver[j]]) {
			hb[i].push_back(ver[j]);
			hbin[ver[j]].push_back(i);
		} else {
			head[blo[i]].push_back(blo[ver[j]]);
			deg[blo[i]][blo[ver[j]]]++;
			ind[blo[ver[j]]]++;
		}
	}
}
int dep[N],q[N+10],l,r;
void bfs() {
	l=1,r=0;
	for(int i=1;i<=totb;++i) {
		if(!ind[i]) q[++r]=i;
	}
	while(l<=r) {
		int u=q[l++],sz;
		sz=head[u].size();
		for(int i=0,v;i<sz;++i) {
			v=head[u][i];
			ind[v]--;
			if(!ind[v]) {
				dep[v]=dep[u]+1;
				q[++r]=v;
			}
		}
	}
}
bool cmp1(int x,int y) {return oud[x]<oud[y];}
bool cmp2(int x,int y) {return ind[x]<ind[y];}
string str;
void clear() {
	for(;tot;--tot) nxt[tot]=0;
	for(int i=1;i<=totb;++i) for(int j=1;j<=totb;++j) {
		deg[i][j]=0;
	}
	for(int i=1;i<=n;++i) {
		first[i]=0;
		b[i].clear();
		head[i].clear();
		hb[i].clear();
		hbin[i].clear();
		blo[i]=dfn[i]=dep[i]=ind[i]=wou[i]=win[i]=0;
	}
	ans=totb=totd=0;
}
int main() {
	ios::sync_with_stdio(0);cin.tie(0);
	cin>>T;
	while(T--) {
		clear();
		cin>>n;
		pw[0]=1;
		for(int i=1;i<=n;++i) {
			pw[i]=(pw[i-1]<<1)%mod;
			if(i>1) pw2[i]=power(2,(i-1)*(i-2)>>1);
		}
		for(int i=2,j,k,c,ed;i<=n;++i) {
			cin>>str;
			for(j=0;j<(i-1)/4+1;++j) {
				ed=i-1-(j<<2);
				c=isdigit(str[j])?str[j]-'0':str[j]-'A'+10;
				for(k=0;k<4&&k<ed;++k) {
					((c>>k)&1)?add(i,(j<<2)+k+1):add((j<<2)+k+1,i);
				}
			}
		}
		for(int i=1;i<=n;++i) {
			if(!blo[i]) tarjan(i,0);
		}
		build();
		bfs();
		for(int i=1;i<=n;++i) {
			oud[i]=hb[i].size();
			ind[i]=hbin[i].size();
		}
		for(int i=1;i<=totb;++i) sort(b[i].begin(),b[i].end(),cmp1);
		for(int i=1,delta,sz;i<=n;++i) {
			if(oud[i]==1) {
				wou[i]=delta=1;
				sz=b[blo[i]].size();
				for(int j=0,v;j<sz;++j) {
					v=b[blo[i]][j];
					if(v!=i&&v!=hb[i][0]&&delta>=oud[v]) {
						wou[i]++,delta++;
					}
				}
			}
		}
		for(int i=1;i<=totb;++i) sort(b[i].begin(),b[i].end(),cmp2);
		for(int i=1,delta,sz;i<=n;++i) {
			if(ind[i]==1) {
				win[i]=delta=1;
				sz=b[blo[i]].size();
				for(int j=0,v;j<sz;++j) {
					v=b[blo[i]][j];
					if(v!=i&&v!=hbin[i][0]&&delta>=ind[v]) {
						win[i]++,delta++;
					}
				}
			}
		}
		for(int i=1,u,v,res;i<=n;++i) {
			u=blo[i];
			for(int j=first[i];j;j=nxt[j]) {
				v=ver[j];
				if(u!=blo[v]) {
					if(dep[u]<dep[blo[v]]-1||deg[u][blo[v]]>1) {
						res=totb-dep[blo[v]]+dep[u];
					} else res=totb;
				} else {
					int sz;
					if(oud[i]==1&&ind[v]==1) {
						res=2,l=1,r=0;
						vis[i]=vis[v]=1;
						q[++r]=i;q[++r]=v;
						while(l<=r) {
							int x=q[l++],y;
							sz=hb[x].size();
							for(int k=0;k<sz;++k) {
								y=hb[x][k];
								ind[y]--;
								if(!ind[y]&&!vis[y]) res++,vis[y]=1,q[++r]=y;
							}
							sz=hbin[x].size();
							for(int k=0;k<sz;++k) {
								y=hbin[x][k];
								oud[y]--;
								if(!oud[y]&&!vis[y]) res++,vis[y]=1,q[++r]=y;
							}
						}
						sz=b[u].size();
						for(int k=0;k<sz;++k) {
							vis[b[u][k]]=0;
							oud[b[u][k]]=hb[b[u][k]].size();
							ind[b[u][k]]=hbin[b[u][k]].size();
						}
						if(res<sz) res+=totb;
						else res+=totb-1;
					} else res=totb+wou[i]+win[v];
	//				cout<<"totb = "<<totb<<" "<<"res = "<<res<<"woui = "<<wou[i]<<"winv = "<<win[v]<<"\n";
				}
	//			printf("j = %d res = %d\n",j,res);
	//			printf("i = %d v = %d woui = %d winv = %d res = %d\n",i,v,wou[i],win[v],res);
				ans=(ans+1ll*pw2[max(i,v)]*pw[min(i,v)-1]%mod*res)%mod;
			}
		}
		cout<<ans<<"\n";
	}
	return 0;
}