/*
朗道永远的神
*/
#include<bits/stdc++.h>
using namespace std;
#define N 5005
#define int long long 
const int p=1e9+7;
int e[N][N],out[N],id[N][N],n,pw[N*N],a[N],s[3][N];
#define pr pair<int,int>
#define mk make_pair
pr b[N];
int C(int n){
    return n*(n-1)>>1;
}
signed main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int T;cin>>T;
    while(T--){
        for(int i=1;i<=n*n;++i)pw[i]=0;
        for(int i=1;i<=n;++i)out[i]=0;
        for(int i=1;i<=n;++i)for(int j=1;j<=n;++j)e[i][j]=0;
        cin>>n;pw[0]=1;
        for(int i=1;i<=n*(n-1)>>1;++i)pw[i]=pw[i-1]*2ll%p;
        for(int i=2;i<=n;++i){
            for(int l=1;l<i;l+=4){
                int r=min(l+3,i-1);
                char c;cin>>c;int v=0;
                if(c>='0'&&c<='9')v=c-'0';
                else v=10+c-'A';
                for(int k=0;l+k<=r;++k){
                    if((v>>k)&1)e[i][l+k]=1,++out[i];
                    else e[l+k][i]=1,++out[l+k];
                }
            }
        }
        int ans=0,res=0;for(int i=1;i<=n;++i)a[i]=out[i];
        sort(a+1,a+n+1);//这个得处理出影响范围啊，一段是-1，一段是+1，一段不变
        for(int i=1,j;i<=n;i=j+1){
            j=i;while(j+1<=n&&a[j+1]==a[i])++j;b[a[i]]=mk(i,j);
        }
        for(int t=0;t<3;++t)for(int i=1,x=0;i<=n;++i)x+=a[i],s[t][i]=s[t][i-1]+(x+t-1==C(i));
        for(int i=2;i<=n;++i)for(int j=1;j<i;++j){
            int mul=pw[(i-2)*(i-1)/2+j-1],l,r;
            if(e[i][j]) l=b[out[j]].first,r=b[out[i]].second;
            else l=b[out[i]].second,r=b[out[j]].first;   
            if(l+1==r&&a[l]+1==a[r])res=s[1][n];
            else if(l<r){
                res=s[1][l-1]+s[1][n]-s[1][r-1];
                res+=s[2][r-1]-s[2][l-1];
            }
            else {
                res=s[1][r-1]+s[1][n]-s[1][l-1];
                res+=s[0][l-1]-s[0][r-1];
            }
            ans+=res*mul%p;
        }
        ans=(ans%p+p)%p;cout<<ans<<"\n";
    }
}
/*
2
3
0
2
6
1
3
7
F
F1
*/