#include <cstdio>
#include <bitset>
using namespace std;
const int N=5003;
int mp[200];
char str[N];
int deg[N];
bitset<N> g[N];
int buc[N],seq[N],pos[N];
int s[N],s1[N],s2[N],s3[N];
int lf[N],rg[N];
void solve(){
	int n;
	scanf("%d",&n);
	for(int i=2;i<=n;++i){
		scanf("%s",str);
		int p=0;
		for(int j=0;j<((i+2)>>2);++j)
			for(int t=0;t<4;++t){
				if(++p>=i) break;
				if(mp[str[j]]>>t&1){
					g[i].set(p);
					++deg[p];
				}
				else ++deg[i];
			}
	}
	for(int i=0;i<=n;++i) buc[i]=0;
	for(int i=1;i<=n;++i) ++buc[deg[i]];
	for(int i=1;i<=n;++i) buc[i]+=buc[i-1];
	for(int i=n;i;--i) seq[buc[deg[i]]--]=deg[i];
	for(int i=1;i<=n;++i) rg[seq[i]]=i;
	for(int i=n;i;--i) lf[seq[i]]=i;
	int sum=0;
	for(int i=1,cur=0;i<=n;++i){
		cur+=seq[i];
		s1[i]=s1[i-1];
		s2[i]=s2[i-1];
		s3[i]=s3[i-1];
		if(cur==(i*(i-1)>>1)) ++s1[i],++sum;
		if(cur==(i*(i-1)>>1)+1) ++s2[i];
		if(cur==(i*(i-1)>>1)-1) ++s3[i];
	}
	int ans=0;
	for(int i=n;i;--i)
		for(int j=i-1;j;--j){
			int res=sum,x,y;
			if(g[i][j]) x=deg[i],y=deg[j];
			else x=deg[j],y=deg[i];
			if(x==y-1){
				ans=(ans*2ll+res)%1000000007;
				continue;
			}
			x=rg[x]-1;y=lf[y]-1;
			if(x<y) res+=s2[y]-s2[x]+s1[x]-s1[y];
			else res=s3[x]-s3[y]+s1[y]-s1[x];
			ans=(ans*2ll+res)%1000000007;
		}
	printf("%d\n",ans);
	for(int i=1;i<=n;++i){
		deg[i]=0;
		for(int j=1;j<i;++j) g[i].reset(j);
	}
}
int main(){
	for(int i=0;i<10;++i) mp[i+'0']=i;
	for(int i=10;i<16;++i) mp[i+'A'-10]=i;
	int tc;
	scanf("%d",&tc);
	while(tc--) solve();
	return 0;
}