#include<bits/stdc++.h>
using namespace std;
#define int long long
#define f(i, a, b) for(int i = (a); i <= (b); i++)
#define cl(i, n) i.clear(),i.resize(n);
#define endl '\n'
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
const int inf = 1e9;
//#define cerr if(false)cerr
//#define freopen if(false)freopen
#define watch(x) cerr  << (#x) << ' '<<'i'<<'s'<<' ' << x << endl
void pofe(int number, int bitnum) {
    string s; f(i, 0, bitnum) {s += char(number & 1) + '0'; number >>= 1; } 
    reverse(s.begin(), s.end()); cerr << s << endl; 
    return;
}
void cmax(int &x, int y) {if(x < y) x = y;}
void cmin(int &x, int y) {if(x > y) x = y;}
//调不出来给我对拍！
int dir[5050][5050];
int deg[5050];
//分段
const int mod = 1e9 + 7;
int qpow(int x, int k) {
    int res = 1; 
    while(k) {
        if(k & 1) res = res * x % mod;
        k >>= 1;
        x = x * x % mod;
    }
    return res;
}
int t[5050];
int tdeg[5050];
int add[5050], mns[5050];
bool cmp(int x, int y) {return deg[x] < deg[y];}
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
    //freopen();
    //freopen();
    //time_t start = clock();
    //think twice,code once.
    //think once,debug forever.
    int T = 1e4; cin >> T; 
    while(T --) {
        int n; cin >> n;
        f(i, 1, n) deg[i] = 0, add[i] = mns[i] = 0;
        f(i, 2, n) {
            int k = (i + 2) / 4; 
            f(j, 1, k) {
                char ch; cin >> ch;
                if(isalpha(ch)) ch = ch - 'A' + 10;
                else ch = ch - '0';
                f(d, 0, 3) {
                    int x = ch & 1;
                    dir[i][4 * j + d - 3] = x;
                    ch >>= 1;
                }
            }
        }
//        f(i, 2, n) f(j, 1, i - 1) cout << dir[i][j] << " \n"[j == i - 1];
        f(i, 2, n) f(j, 1, i - 1) {
            if(dir[i][j] == 1) deg[i] ++;
            else deg[j] ++;
        }
        f(i, 1, n) t[i] = i;
        sort(t + 1, t + n + 1, cmp);
        f(i, 1, n) tdeg[i] = deg[t[i]];
        int num = 0;
        int sum = 0; 
        f(i, 1, n) {
            sum += tdeg[i]; 
            int kp = i * (i - 1) / 2;
            if(sum == kp) {
                num ++;
                add[i] = mns[i] = -1;
            }
            else {
                if(sum == kp - 1) add[i] = 1; //可以 +1 成功
                if(sum == kp + 1) mns[i] = 1; //可以 -1 成功
            }
        }
        // cerr << num << endl;
        // f(i, 1, n) cerr << add[i] << " ";
        // cerr << endl;
        // f(i, 1, n) cerr << mns[i] << " ";
        // cerr << endl;    
        f(i, 2, n) {add[i] = add[i - 1] + add[i]; mns[i] = mns[i - 1] + mns[i];} 
        int res = 0;
        f(i, 2, n) f(j, 1, i - 1) {
            int coe = qpow(2, (i - 2) * (i - 1) / 2 + j - 1);
            int ans = num; int ti = i, tj = j;
            if(deg[i] > deg[j]) swap(ti, tj);
            if(dir[ti][tj] == 1 || deg[ti] == deg[tj]) {
                //ti --, tj ++
                int l = lower_bound(tdeg + 1, tdeg + n + 1, deg[ti]) - tdeg;
                int r = upper_bound(tdeg + 1, tdeg + n + 1, deg[tj]) - tdeg - 1;
                ans += mns[r - 1] - mns[l - 1];
            }
            else {
                int l = upper_bound(tdeg + 1, tdeg + n + 1, deg[ti]) - tdeg - 1;
                int r = lower_bound(tdeg + 1, tdeg + n + 1, deg[tj]) - tdeg;
                if(deg[ti] + 1 == deg[tj]) l = r;
                ans += add[r - 1] - add[l - 1];
            }
            res += coe * ans % mod; res %= mod;
        }
        cout << res << endl;
    }
    //time_t finish = clock();
    //cout << "time used:" << (finish-start) * 1.0 / CLOCKS_PER_SEC <<"s"<< endl;
    return 0;
}
/*
2023/x/xx
start thinking at h:mm


start coding at h:mm
finish debugging at h:mm
*/