#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define For(i,a,b) for(int i=(a);i<=(b);i++)
#define dFor(i,a,b) for(int i=(a);i>=(b);i--)
#define abs_(x) max(x,-(x))
#define tomin(x,y) x=min(x,y)
#define tomax(x,y) x=max(x,y)
#define eq(x,y) (abs_((x)-(y))<=eps) 
#define db double
#define pw(x) ((x)*(x))
#define y1 __
#define vci vector<int> 
#define pb push_back
#define all(x) x.begin(),x.end()
constexpr int N=5e3+5,P=1e9+7;
int read()
{	
	int x=0,y=1;
	char c=getchar();
	for(;!isdigit(c);c=getchar()) if(c=='-') y=0;
	for(;isdigit(c);c=getchar()) x=(x<<3)+(x<<1)+(c^48);
	return y?x:-x;
}
char getc()
{
	char c=getchar();
	for(;!isdigit(c)&&!isalpha(c);c=getchar()) ;
	return c;
}
int turn(char t)
{
	if(isdigit(t)) return t-'0';
	return t-'A'+10;
}
int n;
bool e[N][N];
vector<int> scc[N];
vector<int> e2[N];
int bel[N];
int stk[N],dfn[N],low[N],tot,ct,ct2;
bool vs[N];
int ans[N][N];
void tarjan(int u)
{
//	cout<<"<<"<<u<<"  "<<dfn[u]<<endl;
	vs[u]=1;
	dfn[u]=low[u]=++tot;
	stk[++ct]=u;
	For(v,1,n) if(e[u][v])
	{
		if(!dfn[v]) { tarjan(v); low[u]=min(low[u],low[v]); }
		else if(vs[v]) low[u]=min(low[u],low[v]);
	}
	if(low[u]==dfn[u])
	{
		ct2++;
		do
		{
			int v=stk[ct--];
			vs[v]=0;
			bel[v]=ct2;
			scc[ct2].pb(v);
		}while(stk[ct+1]!=u);
	}
}
int cid[N];
int rd[N];
int q[N];
int Sum;
void tarjan2(int u)
{
	vs[u]=1;
	dfn[u]=low[u]=++tot;
	stk[++ct]=u;
	For(v,1,n) if(e[u][v])
	{
		if(!dfn[v]) { tarjan2(v); low[u]=min(low[u],low[v]); }
		else if(vs[v]) low[u]=min(low[u],low[v]);
	}
	if(low[u]==dfn[u])
	{
		Sum++;
		do
		{
			int v=stk[ct--];
			vs[v]=0;
		}while(stk[ct+1]!=u);
	}
}
void cls()
{
	tot=ct=ct2=0;
	memset(vs,0,n+2);
	memset(dfn,0,n+2<<2);
}
void solve(vector<int> nw)
{
//	cout<<"A";
	int sz=nw.size();
//	cout<<"  "<<sz<<endl;
//	For(i,0,sz-1) cout<<nw[i]<<" "; puts("");
	vector<int> h;
	for(int u:nw)
	{
		if(h.empty()) { h.pb(u); continue; }
		if(e[u][h[0]]) { h.insert(h.begin(),u); continue; }
		if(e[h.back()][u]) { h.pb(u); continue; }
		for(int i=0;i<h.size()-1;i++)
		{
			if(e[h[i]][u]&&e[u][h[i+1]])
			{
				h.insert(h.begin()+i+1,u);
				break;
			}
		}
	}
//	cout<<"B";
//	for(int u:h) cout<<u<<" "; puts("");
	int t=0;
	if(sz==1) goto ok; 
	for(int i=1;;i++)
	{
		if(e[h[i]][h[0]]) { t=i; break; }
	}
	for(int i=t+1;i<sz;i++)
	{
		For(j,0,t)
		{
			if(e[h[i]][h[j]])
			{
				vector<int> ls;
				For(l,j,t) ls.pb(h[l]);
				For(l,0,j-1) ls.pb(h[l]);
				For(l,t+1,i) ls.pb(h[l]);
				For(l,0,i) h[i]=ls[i];
				t=i;
				break;
			}
		}
	}
//	cout<<"C";
//	for(int i=0;i<sz;i++)
//	{
//		int u=h[i],v=h[(i+1)%sz];
//		if(!e[u][v]) puts("FLY");
//	}
	ok: ;
//	puts("FLY");
//	for(int u:nw) cout<<u<<" "; puts(""); 
//	for(int u:h) cout<<u<<" "; puts(""); 
//	return;
	For(i,0,sz-1)
	{
		int u=h[i],v=h[(i+1)%sz];
		e[u][v]=0,e[v][u]=1;
		cls();
		Sum=0;
		For(u,1,n) if(!dfn[u]) tarjan2(u);
		ans[u][v]=Sum;
		e[u][v]=1,e[v][u]=0;
	}
//	cout<<"D";
}
int h[N][N];
int pw2[N*N];
int work()
{
	n=read();
	For(i,1,n) For(j,1,n) e[i][j]=h[i][j]=0;
	For(i,1,n) scc[i].clear();
	For(i,1,n) e2[i].clear();
	
//	int m=n*(n-1)/2;
//	For(i,1,m)
//	{
//		int u=read(),v=read();
//		e[u][v]=1;
//	}
	
	For(i,1,n-1)
	{
		int up=(i+3)>>2;
		For(j,1,up)
		{
			int t=turn(getc()); 
			For(k,0,3)
			{
				bool tt=t>>k&1;
				int t1=i+1,t2=4*j+k-3;
				if(t2<t1)
				{
					if(tt) e[t1][t2]=1;
					else e[t2][t1]=1;
				}
			}
		}
	}

//	For(i,1,n)
//	{
//		For(j,1,n) putchar(e[i][j]+'0'); puts("");
//	}
	cls();
//	puts("FLY");
	For(i,1,n) if(!dfn[i]) tarjan(i);
//	puts("SKY");
	memset(rd,0,n+2<<2);
	For(u,1,n)
	{
		For(v,1,n) if(e[u][v]&&bel[u]!=bel[v])
		{
			int t1=bel[u],t2=bel[v];
			h[t1][t2]++;
			e2[t1].pb(t2);
			rd[t2]++;
		}
	}
	int l=1,r=0;
	For(i,1,ct2) if(!rd[i]) q[++r]=i;
	while(l<=r)
	{
		int u=q[l++];
		cid[u]=l-1;
		for(auto v:e2[u])
		{
			rd[v]--;
			if(!rd[v]) q[++r]=v;
		}
	}
//	cout<<ct2<<endl;
//	puts("RUI");
	For(i,1,n) For(j,1,n) ans[i][j]=ct2;
//	For(i,1,r) cout<<bel[q[i]]<<" "; puts("");
	For(i,1,n) For(j,1,n) if(e[i][j])
	{
		if(bel[i]==bel[j]) continue;
		int u=bel[i],v=bel[j];
		ans[i][j]=ct2-(cid[v]-cid[u]);
		if(cid[v]-cid[u]==1&&h[u][v]==1) ans[i][j]++;
//		cout<<i<<" "<<j<<"  "<<cid[u]<<" "<<cid[v]<<"  "<<u<<" "<<v<<"  "<<ans[i][j]<<endl;
	}
	int tct2=ct2;
	For(i,1,tct2) solve(scc[i]);
	
//	puts("ONE");
	int Ans=0;
	For(i,1,n)
	{
		For(j,1,i-1)
		{
			int t=(e[i][j]?ans[i][j]:ans[j][i]);
			Ans=(Ans+pw2[(i-2)*(i-1)/2+j-1]*1ll*t)%P;
//			cout<<"  "<<j<<" "<<i<<" "<<t<<endl;
		}
	}
	return Ans;
//	For(i,1,n) 
//	{
//		For(j,1,n) putchar(e[i][j]+'0');
//		puts("");
//	}
}
int main()
{
	pw2[0]=1;
	For(i,1,N*N-5) pw2[i]=(pw2[i-1]+pw2[i-1])%P;
	int T=read();
	while(T--) printf("%d\n",work());
	return 0;
}
/*
1
6
1 2
2 3
3 1
4 5
5 6
6 4
1 4
1 5
1 6
2 4
2 5
2 6
3 4
3 5
3 6
*/