#include <bits/stdc++.h>

typedef long long ll;
const int MAX = 5005;
const int INF = MAX;
const int MOD = 1e9 + 7;
int n, T, res, l, r, ans;
int id[MAX], d[MAX], sum[MAX], p0[MAX], p1[MAX], p2[MAX];
char s[MAX];
std::bitset <MAX> g[MAX];
std::pair <int, int> bnd[MAX];

ll qp(ll a, ll x)
{
	ll res = 1;
	while (x) { if (x & 1) { res = res * a % MOD; } a = a * a % MOD; x >>= 1; }
	return res;
}

inline int get(char c) { return (c >= '0' and c <= '9' ? c - '0' : c - 'A' + 10); }
bool cmp(int a, int b) { return d[a] < d[b]; }

void solve()
{
	ans = 0;
	scanf("%d", &n);
	for (int i = 1; i <= n; ++i) { for (int j = 1; j <= n; ++j) { g[i][j] = false; } }
	for (int i = 2; i <= n; ++i)
	{
		scanf("%s", s + 1);
		for (int j = 1; j <= std::ceil(i / 4.0); ++j)
		{
			int p = get(s[j]);
			for (int k = 0; k <= 3 and 4 * j + k - 3 < i; ++k)
			{
				if (p >> k & 1) { g[i][4 * j + k - 3] = true; }
				else { g[4 * j + k - 3][i] = true; }
			}
		}
	}
//	for (int i = 1; i <= n; ++i) { for (int j = 1; j <= n; ++j) { printf("%d ", g[i][j] ? 1 : 0); } printf("\n"); }
	for (int i = 1; i <= n; ++i) { d[i] = 0; }
	for (int i = 1; i <= n; ++i) { for (int j = 1; j <= n; ++j) { if (g[i][j]) { ++d[i]; } } }
	for (int i = 1; i <= n; ++i) { id[i] = i; }
	std::sort(id + 1, id + n + 1, cmp);
	for (int i = 1; i <= n; ++i) { sum[i] = sum[i - 1] + d[id[i]]; }
	for (int i = 1; i <= n; ++i) { bnd[i] = {INF, -INF}; }
	for (int i = 1; i <= n; ++i) { int v = d[id[i]]; bnd[v].first = std::min(bnd[v].first, i); bnd[v].second = std::max(bnd[v].second, i); }
	for (int i = 1; i <= n; ++i)
	{ 
		p0[i] = p0[i - 1] + (sum[i] == (i * (i - 1) / 2));
		p1[i] = p1[i - 1] + ((sum[i] - 1) == (i * (i - 1) / 2));
		p2[i] = p2[i - 1] + ((sum[i] + 1) == (i * (i - 1) / 2));
	}
	for (int i = 1; i <= n; ++i)
	{
		for (int j = i + 1; j <= n; ++j)
		{
			if (g[i][j]) { l = bnd[d[i]].first, r = bnd[d[j]].second; }
			else { l = bnd[d[i]].second, r = bnd[d[j]].first; }
			if ((d[id[l]] + 1 == d[id[r]] and l + 1 == r) or (d[id[r]] + 1 == d[id[l]] and r + 1 == l)) { res = p0[n]; }
			else if (l < r) { res = p0[l - 1] + p0[n] - p0[r - 1] + p1[r - 1] - p1[l - 1]; }
			else { res = p0[r - 1] + p0[n] - p0[l - 1] + p2[l - 1] - p2[r - 1]; }
			ans = (ans + qp(2, 1ll * (j - 1) * (j - 2) / 2 + i - 1) * res % MOD) % MOD;
		}
	}
	printf("%d\n", ans);
}

int main() { scanf("%d", &T); while (T--) { solve(); } }