#include <bits/stdc++.h>
using namespace std;
int T, n, RP;
int E[5005][5005], d[5005], fw[5005], fr[5005], to[5005];
char s[2005];
long long Ans, ton[5005], tonu[5005], tond[5005];
pair < int , int > r[5005];
int Represent (char a){
    if (a >= '0' && a <= '9')
        return a - '0';
    else
        return 10 + a - 'A';
}
void Add (int u, int v){
    E[u][v] = 1;
    E[v][u] = - 1;
    ++ d[v];
}
const long long mod = 1e9 + 7;
long long Qpow (long long a, long long p){
    long long Res = 1;
    while (p > 0){
        if (p & 1)
            Res = Res * a % mod;
        a = a * a % mod;
        p >>= 1;
    }
    return Res;
}
void Clear (){
    Ans = 0;
    RP = 0;
    for (int i = 1;i <= n;++ i)
        ton[i] = tonu[i] = tond[i] = d[i] = 0;
}
int main (){
    scanf ("%d", &T);
    while (T --){
        scanf ("%d", &n);
        for (int i = 2;i <= n;++ i){
            int l = (i - 1) / 4 + 1;
            scanf ("\n%s", s + 1);
            for (int j = 1;j <= l;++ j){
                for (int k = 4 * j - 3, x = Represent (s[j]);k <= 4 * j && k < i;++ k, x >>= 1)
                    if (x & 1)
                        Add (i, k);
                    else
                        Add (k, i);
            }
        }
        for (int i = 1;i <= n;++ i)
            r[i] = make_pair (d[i], i);
        sort (r + 1, r + n + 1);
        int Res = 0;
        int frt = 1;
        for (int i = 1;i <= n;++ i){
            Res += r[i].first;
            to[r[i].second] = i;
            if (r[frt].first != r[i].first)
                frt = i;
            fr[i] = frt;
            if (Res == i * (i - 1) / 2)
                ton[i] = 1, ++ RP;
            if (Res == i * (i - 1) / 2 + 1)
                tonu[i] = 1;
            if (Res == i * (i - 1) / 2 - 1)
                tond[i] = 1;
        }
        int las = n;
        for (int i = n;i >= 1;-- i){
            if (r[i].first != r[las].first)
                las = i;
            fw[i] = las;
        }
        for (int i = 1;i <= n;++ i){
            ton[i] += ton[i - 1];
            tond[i] += tond[i - 1];
            tonu[i] += tonu[i - 1];
        }
        for (int i = 1;i <= n;++ i){
            long long w = Qpow (2, (i - 1) * (i - 2) / 2);
            for (int j = 1;j < i;++ j){
                int u = i, v = j;
                if (E[u][v] < 0)
                    swap (u, v);
                long long p = RP;
                u = to[u];
                v = to[v];
                if (fw[u] != fr[v] - 1){
                    if (fw[u] < fr[v])
                        p += - (ton[fr[v] - 1] - ton[fw[u] - 1]) + tond[fr[v] - 1] - tond[fw[u] - 1];
                    else
                        p += - (ton[fw[u] - 1] - ton[fr[v] - 1]) + tonu[fw[u] - 1] - tonu[fr[v] - 1];
                }
                (Ans += w * p % mod) %= mod;
                (w <<= 1) %= mod;
            }
        }
        printf ("%lld\n", Ans);
        Clear ();
    }
    return 0;
}