#include <bits/stdc++.h>
using namespace std;
int T, n;
int E[5005][5005];
int firs[5005], nex[25000005], to[25000005], tot;
char s[2005];
int idx, dfn[5005], low[5005], bel[5005], sz[5005], cnt, sta[5005], top;
int ct[5005][5005], fw[5005][5005], rd_in_Scc[5005];
vector < int > vet[5005];
bool ins[5005];
long long Ans;
void Clear (){
    for (int i = 1;i <= n;++ i)
        for (int j = 1;j <= n;++ j)
            E[i][j] = ct[i][j] = fw[i][j] = 0;
    for (int i = 1;i <= n;++ i){
        bel[i] = 0;
        sz[i] = 0;
        rd_in_Scc[i] = 0;
        vet[i].clear ();
        firs[i] = 0;
        dfn[i] = low[i] = 0;
    }
    cnt = 0;
    tot = 0;
    idx = 0;
    Ans = 0;
}
void Add (int u, int v){
    E[u][v] = 1;
    E[v][u] = - 1;
    ++ tot;
    nex[tot] = firs[u];
    firs[u] = tot;
    to[tot] = v;
}
int Represent (char a){
    if (a >= '0' && a <= '9')
        return a - '0';
    else
        return 10 + a - 'A';
}
void Tarjan (int u){
    if (dfn[u] > 0)
        return ;
    low[u] = dfn[u] = ++ idx;
    sta[++ top] = u;
    ins[u] = true;
    for (int e = firs[u], v;e;e = nex[e]){
        v = to[e];
        if (dfn[v] == 0){
            Tarjan (v);
            low[u] = min (low[u], low[v]);
        } else
        if (ins[v])
            low[u] = min (low[u], dfn[v]);
    }
    if (dfn[u] == low[u]){
        int v;
        ++ cnt;
        do {
            v = sta[top --];
            ++ sz[cnt];
            bel[v] = cnt;
            ins[v] = false;
            vet[cnt].push_back (v);
        } while (u != v);
        for (int p = 0;p < (int) vet[cnt].size ();++ p)
            for (int e = firs[vet[cnt][p]];e;e = nex[e])
                if (bel[to[e]] == cnt)
                    ++ rd_in_Scc[to[e]];
        for (int p = 0;p < (int) vet[cnt].size ();++ p)
            ++ ct[cnt][rd_in_Scc[vet[cnt][p]]];
        for (int i = sz[cnt];i >= 0;-- i)
            if (rd_in_Scc[i] == 0)
                fw[cnt][i] = i;
            else
                fw[cnt][i] = fw[cnt][i + 1];
    }
}
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;
}
int main (){
    int Q;
    scanf ("%d", &T);
    Q = 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);
            }
        }
        printf ("%d\n", n);
        if (T < Q - 3)
            puts ("0");
        if (T < Q - 3)
            continue;
        for (int i = 1;i <= n;++ i)
            Tarjan (i);
        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);
                if (bel[u] != bel[v]){
                    if (bel[u] - 1 == bel[v])
                        (Ans += w * cnt % mod) %= mod;
                    else
                        (Ans += w * (cnt - (bel[u] - bel[v])) % mod) %= mod;
                } else {
                    int rep = bel[u];
                    int p = 0, lim = sz[rep];
                    -- ct[rep][rd_in_Scc[u]];
                    ++ rd_in_Scc[u];
                    ++ ct[rep][rd_in_Scc[u]];
                    -- ct[rep][rd_in_Scc[v]];
                    -- rd_in_Scc[v];
                    ++ ct[rep][rd_in_Scc[v]];
                    if (ct[rep][rd_in_Scc[u] - 1] == 0)
                        lim = min (lim, rd_in_Scc[u] - 1);
                    if (ct[rep][rd_in_Scc[v] + 1] == 0)
                        lim = min (lim, rd_in_Scc[v] + 1);
                    while (ct[rep][p] > 0){
                        p = fw[rep][p + 1];
                        p = min (p, lim);
                    }
                    -- ct[rep][rd_in_Scc[u]];
                    -- rd_in_Scc[u];
                    ++ ct[rep][rd_in_Scc[u]];
                    -- ct[rep][rd_in_Scc[v]];
                    ++ rd_in_Scc[v];
                    ++ ct[rep][rd_in_Scc[v]];
                    (Ans += w * (cnt + p) % mod) %= mod;
                }
                (w <<= 1) %= mod;
            }
        }
        printf ("%lld\n", Ans);
        Clear ();
    }
    return 0;
}