#include <bits/stdc++.h>
#define INF 1000000000
#define LINF 1000000000000000000
#define mod 1000000007
#define F first
#define S second
#define ll int
#define N 5010
using namespace std;
struct SCC{
	ll n,cnt,cnt2,bel[N],dfn[N],lw[N];
	bool vis[N],inq[N];
	vector<ll> vt[N];
	stack<ll> st;
	void init(ll _n)
	{
		ll i;
		n=_n;
		cnt=cnt2=0;
		for(i=0;i<=n*2;i++)
		{
			vt[i].clear();
			bel[i]=dfn[i]=lw[i]=vis[i]=inq[i]=0;
		}
		while(!st.empty())
		{
			st.pop();
		}
		return;
	}
	void addedge(ll x,ll y)
	{
		vt[x].push_back(y);
		return;
	}
	void dfs(ll x)
	{
		vis[x]=inq[x]=true;
		st.push(x);
		dfn[x]=lw[x]=++cnt;
		ll i;
		for(i=0;i<vt[x].size();i++)
		{
			if(!vis[vt[x][i]])
			{
				dfs(vt[x][i]);
				lw[x]=min(lw[x],lw[vt[x][i]]);
			}
			else if(inq[vt[x][i]])
			{
				lw[x]=min(lw[x],dfn[vt[x][i]]);
			}
		}
		if(lw[x]==dfn[x])
		{
			do
			{
				i=st.top();
				st.pop();
				inq[i]=false;
				bel[i]=cnt2;
			}while(i!=x);
			cnt2++;
		}
		return;
	}
	void solve()
	{
		ll i;
		for(i=0;i<n;i++)
		{
			if(!vis[i])
			{
				dfs(i);
			}
		}
		return;
	}
}gscc;
ll n,ans[N][N],bel[N],deg[N],sid[N],tot,nxt[N],toid[N],chid[N],rt,bannxt,bantp,dfn[N],lw[N],cnt,res;
bool hved[N][N],vis[N];
string s;
vector<ll> vt[N],nt[N],hvnd[N],curnd,chns;
vector<ll> dfschain(ll x)
{
	ll i,j;
	vis[x]=true;
	vector<ll> ret;
	for(i=0;i<vt[x].size();i++)
	{
		if(!vis[vt[x][i]])
		{
			vector<ll> nw=dfschain(vt[x][i]);
			for(j=0;j<nw.size();j++)
			{
				ret.push_back(nw[j]);
			}
		}
	}
	ret.push_back(x);
	return ret;
}
void dfs(ll x)
{
	vis[x]=true;
	dfn[x]=lw[x]=++cnt;
	ll i;
	if(nxt[x]!=-1&&bannxt!=x)
	{
		ll y=nxt[x];
		if(!vis[y])
		{
			dfs(y);
			lw[x]=min(lw[x],lw[y]);
		}
		lw[x]=min(lw[x],dfn[y]);
	}
	if(bantp==x||((!vt[x].empty())&&vt[x][0]==nxt[x]))
	{
		if(vt[x].size()>1)
		{
			ll y=vt[x][1];
			if(!vis[y])
			{
				dfs(y);
				lw[x]=min(lw[x],lw[y]);
			}
			lw[x]=min(lw[x],dfn[y]);
		}
	}
	else if(!vt[x].empty())
	{
		ll y=vt[x][0];
		if(!vis[y])
		{
			dfs(y);
			lw[x]=min(lw[x],lw[y]);
		}
		lw[x]=min(lw[x],dfn[y]);
	}
	if(toid[x]<vt[x].size()&&toid[x]>0)
	{
		ll y=vt[x][toid[x]];
		if(!vis[y])
		{
			dfs(y);
			lw[x]=min(lw[x],lw[y]);
		}
		lw[x]=min(lw[x],dfn[y]);
	}
	res+=(lw[x]==dfn[x]);
	return;
}
void update(ll x,ll y)
{
	ll i;
	for(i=0;i<curnd.size();i++)
	{
		vis[curnd[i]]=false;
	}
	bannxt=-1,bantp=x;
	cnt=res=0;
	dfs(rt);
	ans[min(x,y)][max(x,y)]+=res-1;
	return;
}
void updatenxt(ll x,ll y)
{
	ll i;
	for(i=0;i<curnd.size();i++)
	{
		vis[curnd[i]]=false;
	}
	bannxt=x,bantp=-1;
	cnt=res=0;
	dfs(rt);
	if(!vis[y])
	{
		cnt=0;
		dfs(y);
	}
	ans[min(x,y)][max(x,y)]+=res-1;
	return;
}
bool cmp(ll x,ll y)
{
	return chid[x]<chid[y];
}
void solve(ll id)
{
	ll i,j;
	rt=hvnd[id][0];
	curnd=hvnd[id];
	for(i=0;i<curnd.size();i++)
	{
		vis[curnd[i]]=false;
	}
	chns=dfschain(rt);
	reverse(chns.begin(),chns.end());
	for(i=0;i<chns.size();i++)
	{
		nxt[chns[i]]=(i==chns.size()-1?-1:chns[i+1]);
		chid[chns[i]]=i;
	}
	for(i=0;i<curnd.size();i++)
	{
		sort(vt[curnd[i]].begin(),vt[curnd[i]].end(),cmp);
		toid[curnd[i]]=0;
	}
	for(i=0;i<curnd.size();i++)
	{
		if(!vt[curnd[i]].empty())
		{
			update(curnd[i],vt[curnd[i]][0]);
		}
	}
	for(i=0;i+1<chns.size();i++)
	{
		for(j=0;j<curnd.size();j++)
		{
			while(toid[curnd[j]]<vt[curnd[j]].size()&&(chid[vt[curnd[j]][toid[curnd[j]]]]<=i||vt[curnd[j]][toid[curnd[j]]]==nxt[curnd[j]]))
			{
				toid[curnd[j]]++;
			}
		}
		updatenxt(chns[i],chns[i+1]);
	}
	return;
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	ll i,j,k,T;
	cin>>T;
	while(T--)
	{
		cin>>n;
		for(i=0;i<n;i++)
		{
			vt[i].clear();
		}
		for(i=1;i<n;i++)
		{
			cin>>s;
			for(j=0;j<s.size();j++)
			{
				ll curnum=(s[j]>='0'&&s[j]<='9')?s[j]-'0':s[j]-'A'+10;
				for(k=0;k<4;k++)
				{
					hved[i][j*4+k]=(curnum>>k)&1;
				}
			}
		}
		gscc.init(n);
		for(i=0;i<n;i++)
		{
			for(j=0;j<i;j++)
			{
				if(hved[i][j])
				{
					vt[i].push_back(j);
					gscc.addedge(i,j);
				}
				else
				{
					vt[j].push_back(i);
					gscc.addedge(j,i);
				}
			}
		}
		gscc.solve();
		tot=gscc.cnt2;
		for(i=0;i<n;i++)
		{
			bel[i]=gscc.bel[i];
			hvnd[bel[i]].push_back(i);
			for(j=0;j<i;j++)
			{
				ans[j][i]=tot;
			}
		}
		for(i=0;i<n;i++)
		{
			for(j=0;j<vt[i].size();j++)
			{
				if(bel[i]!=bel[vt[i][j]])
				{
					nt[bel[i]].push_back(bel[vt[i][j]]);
					deg[bel[vt[i][j]]]++;
				}
			}
		}
		queue<ll> q;
		for(i=0;i<tot;i++)
		{
			if(deg[i]==0)
			{
				q.push(i);
				sid[i]=0;
			}
		}
		while(!q.empty())
		{
			ll x=q.front();
			q.pop();
			for(i=0;i<nt[x].size();i++)
			{
				deg[nt[x][i]]--;
				if(deg[nt[x][i]]==0)
				{
					sid[nt[x][i]]=sid[x]+1;
					q.push(nt[x][i]);
				}
			}
		}
		for(i=0;i<n;i++)
		{
			for(j=0;j<i;j++)
			{
				if(bel[i]!=bel[j])
				{
					ans[j][i]-=abs(sid[bel[i]]-sid[bel[j]]);
					if(abs(sid[bel[i]]-sid[bel[j]])==1&&hvnd[bel[i]].size()==1&&hvnd[bel[j]].size()==1)
					{
						ans[j][i]++;
					}
				}
			}
		}
		for(i=0;i<n;i++)
		{
			vector<ll> nw;
			for(j=0;j<vt[i].size();j++)
			{
				if(bel[i]==bel[vt[i][j]])
				{
					nw.push_back(vt[i][j]);
				}
			}
			vt[i]=nw;
		}
		for(i=0;i<tot;i++)
		{
			solve(i);
		}
		ll curpw=1;
		long long res=0;
		for(i=0;i<n;i++)
		{
			for(j=0;j<i;j++)
			{
				res=(res+(long long)ans[j][i]*(long long)curpw)%mod;
				curpw=(curpw+curpw)%mod;
			}
		}
		cout<<res<<endl;
	}
	return 0;
}