#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];
int pre[5005],nxt[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;
}
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]++;
		}
		for (int i=0;i<n;i++){
			pre[i]=nxt[i]=i;
			for (int j=0;j<n;j++){
				if (a[c[i]][c[j]]==1)pre[i]=min(pre[i],j);
				if (a[c[j]][c[i]]==1)nxt[i]=max(nxt[i],j);
			}
		}
		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){
					int cnt=0;
					int p=x+1;
					int l=-1,r=-1;
					for (int i=x;i>=0;i--){
						if (i<p){
							if (i<x&&l==-1)l=p;
							cnt++;
						}
						p=min(p,pre[i]);
					}
					if (l==-1)l=0;
					p=y-1;
					for (int i=y;i<n;i++){
						if (i>p){
							if (i>y&&r==-1)r=p;
							cnt++;
						}
						p=max(p,nxt[i]);
					}
					if (r==-1)r=n-1;
					int fg=0;
					p=n;
					for (int i=l;i<=x;i++)
						for (int j=y;j<n;j++)
							if ((i!=x||j!=y)&&a[c[i]][c[j]]==1){
								if (j<=r)fg=1;
								p=min(p,j);
							}
					for (int i=p;i<n;i++)
						if (pre[i]<=x)fg=1;
					if (fg==0)sum=(sum+1ll*t*cnt)%mod;
					else sum=(sum+1ll*t*(ans-(s0[y]-s0[x])))%mod;
				}
				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;
}