#include<bits/stdc++.h>
#define LL long long
#define SZ(x) ((LL)(x.size()))
using namespace std;
long long read(){
  long long q=0,w=1;
  char ch=getchar();
  while(ch>'9' || ch<'0'){if(ch=='-')w=-1;ch=getchar();}
  while(ch>='0'&&ch<='9'){q=q*10+(ch-'0');ch=getchar();}
  return q*w;
}
void write(LL x){
  if(x<0){putchar('-');x=(-x);}
  if(x>9)write(x/10);
  putchar('0'+x%10);
}
void writeln(LL x){write(x);puts("");}
void writecs(LL x){write(x);putchar(' ');}
const long long mod = 1000000007;
void addmod(LL &x,LL y){x+=y;if(x>=mod)x-=mod;}
const long long N = 5000+95;
long long T,n,b[N];char ch[N];bool e[N][N];
LL get(char c){
  if('0'<=c&&c<='9')return (LL)(c-'0');
  else return (LL)(c-'A'+10);
}
long long in[N],lim[N],cnt[N],seq[N],idx[N],sum[N],val[N],ans[N][N];
void print(){
  LL pw=1,ns=0;
  for(LL i=1;i<=n;i++)
    for(LL j=1;j<i;j++){
      addmod(ns,pw*ans[i][j]%mod);
      pw=(pw*2)%mod;
    }
  writeln(ns);
  return ;
}
int main(){
  T=read();
  while(T--){
    n=read();
    for(LL i=1;i<=n;i++)
      for(LL j=1;j<i;j++)e[i][j]=false;
    for(LL i=2;i<=n;i++){
      scanf("%s",ch+1);
      for(LL j=1;j<=((i+3)>>2);j++){
	LL v=get(ch[j]);
	for(LL k=(j<<2)-3;k<=min((j<<2),i-1);k++){e[i][k]=(v&1);v>>=1;}
      }
    }
    for(LL i=1;i<=n;i++)
      for(LL j=i+1;j<=n;j++)
	e[i][j]=(e[j][i]^1);
    /*    for(LL i=1;i<=n;i++){
      for(LL j=1;j<=n;j++)
	cout<<e[i][j]<<" ";
      cout<<endl;
    }*/
    for(LL i=1;i<=n;i++)
      lim[i]=((i*(i-1))>>1);
    for(LL i=0;i<=n;i++)in[i]=cnt[i]=0;
    for(LL i=1;i<=n;i++)
      for(LL j=1;j<=n;j++)
	if(e[i][j])in[j]++;
    /*    for(LL i=1;i<=n;i++)
      cout<<in[i]<<" ";
    cout<<endl;*/
    for(LL i=1;i<=n;i++)cnt[in[i]]++;
    for(LL x=1;x<=n;x++){
      if(!in[x])continue;
      cnt[in[x]]--;cnt[in[x]-1]++;
      LL top=0;
      for(LL i=0;i<=n;i++)
	for(LL k=1;k<=cnt[i];k++)
	  seq[++top]=i;
      /*      cout<<" x = "<<x<<" seq: "<<endl;
      for(LL i=1;i<=n;i++)
	cout<<seq[i]<<" ";
      cout<<endl;*/
      for(LL i=1;i<=n;i++)
	idx[seq[i]]=i;
      LL base=0;
      for(LL i=1;i<=n;i++){
	sum[i]=sum[i-1]+seq[i];
	if(sum[i]==lim[i])base++;
      }
      for(LL i=n;i>=1;i--){
	val[i]=val[i+1];
	//	cout<<"  i = "<<i<<" sum[i] = "<<sum[i]<<" lim[i] = "<<lim[i]<<endl;
	if(sum[i]==lim[i]-1)val[i]++;
	if(sum[i]==lim[i])val[i]--;
	//	cout<<"   i = "<<i<<" val[i] = "<<val[i]<<endl;
      }
      
      for(LL y=1;y<=n;y++){
	if(!e[y][x])continue;
	//	cout<<" -> y = "<<y<<" in[y] = "<<in[y]<<endl;
	LL pos=idx[in[y]];
	//	cout<<" pos = "<<pos<<endl;
	ans[max(x,y)][min(x,y)]=base+val[pos];
	//	cout<<" min(x,y) = "<<min(x,y)<<" max(x,y) = "<<max(x,y)<<endl;
      }
      cnt[in[x]-1]--;cnt[in[x]]++;
    }
    /*    for(LL i=1;i<=n;i++)
      for(LL j=1;j<i;j++)
	cout<<" i = "<<i<<" j = "<<j<<" ans[i][j] = "<<ans[i][j]<<endl;*/
    print();
  }
  return 0;
}