#include <bits/stdc++.h>
using namespace std;

const int N = 5010, mod = 1e9 + 7;
int T, n, a[N], d[N], fir[N * N], lst[N * N];
char str[N];
bool mp[N][N];

int s[3][N];
void init() {
	for (int i=1; i<=n; ++i) a[i] = d[i];
	sort(a + 1, a + n + 1);
	for (int i=1; i<=n; ++i) lst[a[i]] = i;
	for (int i=n; i; --i) fir[a[i]] = i;
	for (int i=1; i<=n; ++i) {
		a[i] += a[i - 1];
		int num = i * (i - 1) / 2;
		for (int j=0; j<3; ++j)
			s[j][i] = s[j][i - 1] + (a[i] == num + j - 1);
	}
}
int query(int i, int l, int r) {
	return s[i][r] - s[i][l - 1];
}
int work(int u, int v) {
	if (!mp[u][v]) swap(u, v);
	if (d[u] + 1 == d[v]) return query(1, 1, n);
	int l = lst[d[u]], r = fir[d[v]], sgn = 2;
	if (l > r) swap(l, r), sgn = 0;
	return query(1, 1, l - 1) + query(sgn, l, r - 1) + query(1, r, n);
}

int main() {
	scanf("%d", &T);
	while (T--) {
		scanf("%d", &n);
		for (int i=1; i<=n; ++i) d[i] = 0;
		for (int i=2; i<=n; ++i) {
			scanf("%s", str + 1);
			int len = strlen(str + 1);
			for (int j=1; j<=len; ++j) {
				int num = isdigit(str[j]) ? (str[j] - '0') : (10 + str[j] - 'A');
				for (int k=0; k<=3; ++k) {
					int x = 4 * j + k - 3;
					if (x < i) {
						mp[i][x] = ((num >> k) & 1);
						mp[x][i] = mp[i][x] ^ 1;
						d[x] += mp[i][x], d[i] += mp[x][i];
					}
				}
			}
		}
		init();
		int ans = 0;
		for (int i=n; i; --i)
			for (int j=i-1; j; --j)
				ans = ((ans << 1) + work(i, j)) % mod;
		printf("%d\n", ans);
	}
	return 0;
}