//I play to win
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define pi pair<int,int>
#define ld long double
#define vi vector<int>
#define all(x) begin(x),end(x)
using namespace std;
inline ll read()
{
    ll x=0,f=1;char c=getchar();
    for(;!isdigit(c);c=getchar())if(c=='-')f=-1;
    for(;isdigit(c);c=getchar())x=(x<<3)+(x<<1)+(c^48);
    return x*f;
}
inline void out(ll x){if(x>9)out(x/10);putchar(x%10^48);}
inline void print(ll x,char c='\n'){if(x<0)putchar('-'),x=-x;out(x),putchar(c);}
const int N=5005,p=1e9+7;
char str[N];
int e[N][N],d[N],id[N],s[N],pw[N*N],suf[N],pre[N],c1[N],c2[N];
void solve()
{
    int n=read();ll ans=0;
    for(int i=1;i<=n;i++)d[i]=c1[i]=c2[i]=0,id[i]=i,memset(e[i]+1,0,n<<2);
    for(int i=1;i<n;i++)
    {
        scanf("%s",str+1);
        for(int j=1;j<=(i+3)/4;j++)
        {
            int v=(str[j]<='9')?(str[j]-'0'):(str[j]-'A'+10);
            for(int k=0;k<4;k++)
            {
                int x=i+1,y=4*j+k-3;
                if(y>=x)continue;
                if(v>>k&1^1)swap(x,y);
                e[x][y]=1,d[x]++;
            }
        }
    }
    sort(id+1,id+n+1,[&](int x,int y){return d[x]<d[y];});
    for(int i=1;i<=n;c1[i]+=c1[i-1],c2[i]+=c2[i-1],i++)
        if((s[i]=d[id[i]]+s[i-1])==i*(i-1)/2)c1[i]++;
        else if(s[i]+1==i*(i-1)/2)c2[i]++;
    pre[1]=1,suf[n]=n;
    for(int i=2;i<=n;i++)pre[i]=(d[id[i]]==d[id[i-1]])?pre[i-1]:i;
    for(int i=n-1;i;i--)suf[i]=(d[id[i]]==d[id[i+1]])?suf[i+1]:i;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
        {
            int x=id[i],y=id[j];
            if(e[x][y])
            {
                ll res=c1[n];
                if(d[x]!=d[y]+1)
                {
                    int l=pre[i],r=suf[j];
                    assert(l!=r);
                    if(l<r)res+=c2[r-1]-c2[l-1];
                    else res-=c1[l-1]-c1[r-1];
                }
                if(x<y)swap(x,y);
                ans+=pw[(x-2)*(x-1)/2+y-1]*res%p;
            }
        }
    print(ans);
}
int main()
{
    pw[0]=1;
    for(int i=1;i<N*N;i++)pw[i]=pw[i-1]*2%p;
    int T=read();
    while(T--)solve();
}