#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
#define mod 1000000007
using namespace std;
int pow_2[25000005]; 
int t,n,a[5005][5005];
char str[5005];
int pos[5005];
int ch[5005],s0[5005],s1[5005];
vector<int> work(int l,int r){
	if (l==r){
		vector<int> ans;
		ans.push_back(l);
		return ans;
	}
	int mid=(l+r)/2;
	vector<int> cl=work(l,mid),cr=work(mid+1,r);
	vector<int> c;
	int i=0,j=0;
	while(i<(int)cl.size()&&j<(int)cr.size()){
		if (a[cl[i]][cr[j]]==1)c.push_back(cl[i++]);
		else c.push_back(cr[j++]);
	}
	while(i<(int)cl.size())c.push_back(cl[i++]);
	while(j<(int)cr.size())c.push_back(cr[j++]);
	return c;
}
namespace Brute{
	int m,u[100005],v[100005],first[100005],nxt[100005];
	void add_edge(int a,int b){
		int i=++m;
		u[i]=a,v[i]=b;
		nxt[i]=first[u[i]],first[u[i]]=i;
		return;
	}
	int idx,dfn[100005],low[100005];
	int tot,sta[100005],in_sta[100005];
	int col_tot;
	void init(){
		m=0;
		for (int i=1;i<=n;i++)first[i]=dfn[i]=low[i]=in_sta[i]=0;
		idx=tot=col_tot=0;
		return;
	}
	void dfs(int now){
		sta[++tot]=now;
		in_sta[now]=1;
		dfn[now]=low[now]=++idx;
		for (int i=first[now];i;i=nxt[i]){
			if (dfn[v[i]]==0)dfs(v[i]),low[now]=min(low[now],low[v[i]]);
			else if (in_sta[v[i]]==1)low[now]=min(low[now],dfn[v[i]]);
		}
		if (dfn[now]==low[now]){
			++col_tot;
			while(sta[tot]!=now)in_sta[sta[tot--]]=0;
			in_sta[sta[tot--]]=0;
		}
		return;
	}
	int work(){
		for (int i=1;i<=n;i++)
			if (dfn[i]==0)dfs(i);
		return col_tot;
	}
}
int main(){
	pow_2[0]=1;
	for (int i=1;i<=25000000;i++)pow_2[i]=pow_2[i-1]*2%mod;
	cin>>t;
	while(t--){
		cin>>n;
		for (int i=1;i<n;i++){
			scanf("%s",str+1);
			for (int j=1;j<=(i+3)/4;j++){
				int x=0;
				if (str[j]>='0'&&str[j]<='9')x=str[j]-'0';
				else x=str[j]-'A'+10;
				for (int k=0;k<4&&4*j+k-3<=i;k++){
					a[i+1][4*j+k-3]=((x>>k)&1);
					a[4*j+k-3][i+1]=1-((x>>k)&1);
				}
			}
		}
		vector<int> c=work(1,n);
		for (int i=0;i<n;i++)pos[c[i]]=i;
		memset(ch,0,sizeof(ch));
		for (int i=1;i<=n;i++)
			for (int j=1;j<=n;j++)
				if (a[i][j]==1&&pos[i]>pos[j]){
					ch[pos[j]+1]++;
					ch[pos[i]+1]--;
				}
		int ans=1;
		for (int i=1;i<n;i++){
			ch[i]+=ch[i-1];
			s0[i]=s0[i-1],s1[i]=s1[i-1];
			if (ch[i]==0)s0[i]++,ans++;
			if (ch[i]==1)s1[i]++;
		}
		int sum=0;
		for (int i=1;i<=n;i++)
			for (int j=1;j<i;j++){
				int x=pos[i],y=pos[j];
				if (a[i][j]==0)swap(x,y);
				int t=pow_2[(i-2)*(i-1)/2+j-1];
				if (y==x+1){
					Brute::init();
					a[i][j]^=1,a[j][i]^=1;
					for (int k=1;k<=n;k++)
						for (int l=1;l<=n;l++)
							if (a[k][l]==1)Brute::add_edge(k,l);
					sum=(sum+1ll*t*Brute::work())%mod;
					a[i][j]^=1,a[j][i]^=1;
				}
				else{
					if (x<y)sum=(sum+1ll*t*(ans-(s0[y]-s0[x])))%mod;
					else sum=(sum+1ll*t*(ans+(s1[x]-s1[y])))%mod;
				}
			}
		cout<<sum<<endl;
	}
	return 0;
}