#include <bits/stdc++.h>
#include <ext/pb_ds/priority_queue.hpp>

using namespace std;

using ci = const int;

using u32 = uint32_t;
using i64 =  int64_t;
using u64 = uint64_t;

#define il inline
#define TT template<class T>

TT il void Max(T &x, const T &y) { if (x < y) x = y; }
TT il void Min(T &x, const T &y) { if (y < x) x = y; }

struct TimeCalc {
	~TimeCalc() { cerr << clock() * 1.0 / CLOCKS_PER_SEC; }
} TimeCalc;

const int N = 5005;
const int mod = 1e9 + 7;

int T, n;
char str[N];
bitset<N> e[N];
int d[N], s[N], s0[N], s1[N], sz[N];

il int C2(int x) { return x * (x - 1) / 2; }

void work() {
	scanf("%d", &n);
	for (int i = 2; i <= n; ++i) {
		scanf("%s", str + 1);
		for (int j = 1, x, p = 1; j <= (i + 3) / 4; ++j) {
			x = str[j] >= 'A' ? str[j] - 'A' + 10 : str[j] - '0';
			for (int k = 0; k < 4; ++k, ++p) {
				if (p >= i) break;
				if (x >> k & 1) e[i]._Unchecked_set(p), ++d[i];
				else e[p]._Unchecked_set(i), ++d[p];
			}
		}
	}

	memcpy(s, d, sizeof(int) * (n + 1));
	sort(s + 1, s + 1 + n);

	for (int i = 1; i <= n; ++i) {
		s[i] += s[i - 1];
		s0[i] = s0[i - 1] + (s[i] == C2(i));
		s1[i] = s1[i - 1] + (s[i] == C2(i) + 1);
	}

	for (int i = 1; i <= n; ++i) ++sz[d[i]];
	for (int i = 1; i <= n; ++i) sz[i] += sz[i - 1];

	int ans = 0;
	for (int i = n; i >= 1; --i) {
		for (int j = i - 1; j; --j) {
			int x = i, y = j, z = s0[n];
			if (e[x][y]) swap(x, y);

			/**
			 * for d[x] >= d[y]
			 * 交换前在同一个强连通分量中，只需贡献新增的量
			 * 
			 * for d[x] + 1 < d[y]
			 * 交换后在同一个强连通分量中，与上述相反
			 */
			if (d[x] >= d[y]) z += s1[sz[d[x]] - 1] - s1[sz[d[y] - 1]];
			if (d[x] + 1 < d[y]) z -= s0[sz[d[y] - 1]] - s0[sz[d[x]] - 1];
			ans = (ans * 2 + z) % mod;
		}
	}

	printf("%d\n", ans);

	for (int i = 1; i <= n; ++i) e[i].reset();
	memset(d, 0, sizeof(int) * (n + 1));
	memset(sz, 0, sizeof(int) * (n + 1));
}

int main() {
#ifndef ONLINE_JUDGE
	freopen(".in", "r", stdin);
	freopen(".out", "w", stdout);
#endif

	scanf("%d", &T);
	while (T--) {
		work();
	}

	return 0;
}