/* 陽炎は黄泉に待たむと。*/

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

#define inl inline
constexpr int BUF = 1<<17;
char ibuf[BUF], obuf[BUF], *__st, *__ed, *__pt;
inl void buffer () { __st = ibuf,
	__ed = ibuf + fread (ibuf, 1, BUF, stdin); }
inl void flush () {
	fwrite (obuf, 1, __pt - obuf, stdout);
	__pt = obuf; }
inl char getc () {
	return __st == __ed && (buffer (),
		__st == __ed) ? EOF : *__st++; }
inl void putc (char c) {
	if (__pt == obuf + BUF) flush ();
	*__pt++ = c; }
template <typename T> inl bool read (T &x) {
	int f = 1; static char c = getc (); x = 0; 
	for (; ~c && !isdigit (c); c = getc ())
		if (c == '-') f = -1;
	if (c == EOF) return 0;
	for (; ~c && isdigit (c); c = getc ())
		x = (x<<1) + (x<<3) + (c^48);
	x *= f; return 1;
}
inl int read (char *s) {
	static char c = getc ();
	for (; ~c && isspace (c); c = getc ());
	if (c == EOF) return 0; int len = 0;
	for (; ~c && !isspace (c); c = getc ())
		*s++ = c, ++len; return *s = 0, len;
}
template <typename T, typename...Targs>
inl bool read (T &x, Targs&... args) {
	return read (x) && read (args...); }
template <typename T> inl void print (T x) {
	if (x < 0) x = -x, putc ('-');
	static int st[36], top = 0;
	do { st[top++] = x % 10, x /= 10; } while (x);
	while (top) putc (st[--top] ^ '0');
}
template <typename T> inl void print (T *s) {
	for (; *s; ++s) putc (*s); }
template <typename T>
inl void print (T x, char c) {
	print (x), putc (c); }
template <typename T, typename...Targs>
inl void print (T x, Targs...args) {
	print (x), putc (' '), print (args...); }
struct IO {
	IO () { __pt = obuf, __ed = __st = ibuf; }
	~IO () { flush (); }
} __io;
#define putchar putc
#define puts(s) (print (s, '\n'))
#define scanf(...) fprintf (stderr, "fread loaded.")
#define printf scanf

typedef long long ll;
typedef unsigned long long ull;
// typedef __int128 lll;
// typedef long double llf;
typedef pair <int, int> pint;
#define fst first
#define scd second
#define all(p) begin (p), end (p)
#define empb emplace_back

#ifdef SHIKEN
#define msg(args...) fprintf (stderr, args)
#else
#define msg(...) void ()
#endif

constexpr int N = 5005, G = N/4 + 2, P = 1e9 + 7;
int T, n; char s[G]; bool vis[N], ins[N], e[N][N];
short ind[N], tt[N], bel[N], siz[N], c;
int pow2c[N], pow2u[N]; ll ans;

template <short bel[], short siz[]>
int imple () {
	static short p[N];
	memset (tt, 0, n + 1<<1);
	for (int x = 0; x < n; ++x)
		++tt[ind[x]];
	for (int d = 1; d <= n; ++d)
		tt[d] += tt[d - 1];
	for (int x = 0; x < n; ++x)
		p[tt[ind[x]]--] = x;
	int c = 0;
	for (int i = 0, j = 1, sum = 0; j <= n; sum = 0, i = j, ++j) {
		bel[p[j]] = ++c;
		auto &s = siz[c] = 1;
		while (sum += ind[p[j]], sum != ((j - i) * (j + i - 1)>>1))
			bel[p[++j]] = c, ++s;
	}
	return c;
}

inl void calc (const int x, const int y) {
	static short bel[N], siz[N];
	const bool jun = e[x][y];
	if (jun) ++ind[x], --ind[y];
	else ++ind[y], --ind[x];
	const int _c = imple <bel, siz> ();
	if (!jun) ++ind[x], --ind[y];
	else ++ind[y], --ind[x];
	ans += (ll) pow2c[max (x, y)] * pow2u[min (x, y)] % P * (_c - c);
}
bool route (int x, const int b, int u[], int &uc) {
	u[uc++] = x; ins[x] = 1;
	for (int y = 0; y < n; ++y)
		if (bel[y] == b && e[x][y] && vis[y])
			return calc (x, y), 1;
	for (int y = 0; y < n; ++y)
		if (bel[y] == b && e[x][y] && !ins[y] && route (x, b, u, uc))
			return calc (x, y), 1;
	for (int y = 0; y < n; ++y)
		if (bel[y] == b && e[x][y] && ins[y])
			return calc (x, y), 0;
	return 0;
}
inl void sousaku (const int id) {
	static int u[N], uc, pt;
	uc = pt = 0; int rt = 0;
	while (bel[rt] != id) ++rt;
	vis[rt] = 1; u[uc++] = rt;
	while (pt < uc) {
		const int x = u[pt]; bool on = 0;
		for (int y = 0; y < n; ++y) {
			if (bel[y] != id || vis[y] || !e[x][y]) continue;
			on = 1; int _uc = uc;
			calc (x, y);
			route (y, id, u, uc);
			while (_uc < uc) vis[u[_uc++]] = 1;
		}
		if (!on) ++pt;
	}
}

int main () {
	/*  */
pow2c[0] = pow2u[0] = 1;
for (int i = 1; i < N; ++i)
	pow2u[i] = (pow2u[i - 1]<<1) % P,
	pow2c[i] = pow2c[i - 1] * (ll) pow2u[i - 1] % P;

read (T);
while (T--) {
	read (n); ans = 0;
	memset (ind, 0, n + 1<<1);
	memset (vis, 0, n + 1);
	memset (ins, 0, n + 1);
	for (int x = 1; x < n; ++x) {
		read (s);
		for (int i = 0; (i<<2) <= x; ++i) {
			char &c = s[i];
			c = c >= 'A' ? c - 'A' + 10 : c - '0';
		}
		e[x][x] = 0;
		for (int y = 0; y < x; ++y) {
			const bool jun = (s[y>>2]>>(y & 3)) & 1;
			e[x][y] = jun, e[y][x] = !jun;
			ind[y] += jun, ind[x] += !jun;
			ans += (ll) pow2c[x] * pow2u[y] % P;
		}
	}
	c = imple <bel, siz> ();
	(ans %= P) *= c;
	for (int b = 0; b < c; ++b) sousaku (b);
	for (int x = 0; x < n; ++x)
		for (int y = 0; y < x; ++y) {
			const int b1 = bel[x], b2 = bel[y], dt = abs (b1 - b2);
			if (b1 == b2) continue;
			if (dt == 1 && siz[b2] == 1 && siz[b1] == 1);
			else ans -= (ll) pow2c[x] * pow2u[y] % P * dt;
		}
	print ((ans % P + P) % P); putc ('\n');
}

	return 0;
}