#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;
}
int get_ans(){
	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];
		if (ch[i]==0)ans++;
	}
	return ans;
} 
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];
				int t=pow_2[(i-2)*(i-1)/2+j-1];
				a[i][j]^=1,a[j][i]^=1;
				sum=(sum+1ll*t*get_ans())%mod;
				a[i][j]^=1,a[j][i]^=1;
//				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;
}