// 
/*
由兰道定理得，竞赛图的强连通分量个数为 $\sum_{i=1}^{n}[\sum_{j=1}^i out_j=C(i,2)]$。
每次反转一条边可以做到 O(1) 修改。 
*/
#include<bits/stdc++.h>
#define int long long
typedef long long ll;
using namespace std;
const int N = 5005;
const ll mod = 1e9 + 7;
bool flg[N][N];
int n;
char s[N];
int out[N], sum[N], nxt[N]; 
int cnt1[N], cnt2[N];
int turn(char x) {return (x >= '0' && x <= '9' ? (x - '0') : (10 + (x - 'A')));}
void solve() {
	scanf("%lld", &n);
	for(int i = 1; i <= n; i++) out[i] = 0;
	for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) flg[i][j] = false;
	for(int i = 2, l; i <= n; i++) { l = (i - 1) / 4 + 1;
        cin>>(s + 1);
        for(int j = 1; j <= l; j++) for(int k = 4 * j - 3, x = turn(s[j]); k <= 4 * j && k < i; k++, x >>= 1) 
			if(x & 1) flg[i][k] = true, flg[k][i] = false, out[i]++;
			else flg[k][i] = true, flg[i][k] = false, out[k]++;
    }
    for(int i = 1; i <= n; i++) sum[i] = out[i], nxt[i] = 0;
    for(int i = 1; i <= n; i++) nxt[sum[i]]++;
	sort(sum + 1, sum + n + 1);
	for(int i = 1; i <= n; i++) nxt[i] += nxt[i - 1];
	for(int i = 1; i <= n; i++) {
		int p = i * (i - 1) / 2; sum[i] += sum[i - 1];
		cnt1[i] = cnt1[i - 1], cnt2[i] = cnt2[i - 1];
		if(sum[i] == p) cnt1[i]++;
		else if(sum[i] - 1 == p) cnt2[i]++;
	} 
	ll ans = 0;
	for(int i = n; i >= 1; i--) for(int j = i - 1; j >= 1; j--) {
		int sum = cnt1[n], x = i, y = j;
		if(flg[x][y]) swap(x, y);
		if(out[x] >= out[y]) sum += (cnt2[nxt[out[x]] - 1] - cnt2[nxt[out[y] - 1]]);
		if(out[x] + 1 < out[y]) sum -= (cnt1[nxt[out[y] - 1]] - cnt1[nxt[out[x]] - 1]);
		ans = (ans * 2 + sum) % mod;
	}
	printf("%lld\n", ans);
}
signed main() {
	int t; cin>>t;
	while(t--) solve();
	return 0;
}