#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>
#define mod 1000000007
using namespace std;
const int N = 5005;char tp[N];
int t, n, a[N], id[N], rk[N], le[N], ri[N], to[N][N], ans, s0[N], s1[N], s2[N];
int main(){scanf("%d", &t);
	while (t --){scanf("%d", &n), id[1] = 1, a[1] = 0, ans = 0;
		for (int i = 2;i <= n;i ++){scanf("%s", tp), id[i] = i, a[i] = 0;
			for (int j = 0;j < i - 1;j ++) a[i] += 
			to[i][j + 1] = (tp[j >> 2] >= 'A' ? tp[j >> 2] - 'A' + 10 : tp[j >> 2] - '0') >> (j & 3) & 1;
			for (int j = 1;j < i;j ++) a[j] += 1 - to[i][j];
		}sort(id + 1, id + n + 1, [&](int x, int y){return a[x] < a[y];});
		for (int i = 1;i <= n;i ++) rk[id[i]] = i;
		sort(a + 1, a + n + 1);
		for (int i = 1;i <= n;i ++){
			if (i > 1 && a[i] == a[i - 1])
			le[i] = le[i - 1];else le[i] = i;
		}
		for (int i = n;i >= 1;i --){
			if (i < n && a[i] == a[i + 1])
			ri[i] = ri[i + 1];else ri[i] = i;
		}
		for (int i = 1, sm = 0;i <= n;i ++) s0[i] = s0[i - 1] + ((sm += a[i]) == i * (i - 1) / 2);
		for (int i = 1, sm = 0;i <= n;i ++) s1[i] = s1[i - 1] + ((sm += a[i]) == i * (i - 1) / 2 + 1);
		for (int i = 1, sm = 0;i <= n;i ++) s2[i] = s2[i - 1] + ((sm += a[i]) == i * (i - 1) / 2 - 1);
		for (int i = n, tmp, lp, rp;i >= 2;i --){
			for (int j = i - 1;j >= 1;j --){
				if (to[i][j]) swap(i, j);tmp = s0[n];int l = rk[i], r = rk[j];
				if (a[l] + 1 == a[r]) goto Calc; 
				if (l < r) tmp += s1[r - 1] - s1[l - 1] - s0[r - 1] + s0[l - 1];
				else tmp += s2[l - 1] - s2[r - 1] - s0[l - 1] + s0[r - 1];
				Calc: ans = (ans * 2 + tmp) % mod;
				if (to[j][i]) swap(i, j);
			}
		}printf("%d\n", ans);
	}
}
// 2 0 1
// 3 
// i -> j  cd[i] --, cd[j] ++
// j -> i  cd[j] --, cd[i] ++ (swap(i, j))