#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int mod = 1e9+7;
int t, n, sum[5005], sum0[5005], sum1[5005], sum2[5005];
bool book[5005][5005];
int place[5005], L[5005], R[5005];
struct e{
	int i, u;
}a[5005];
bool cmp(e x, e y) {
	return x.u<y.u;
}
int main() {
	scanf("%d", &t);
	for (int zqw=1;zqw<=t;zqw++) {
		scanf("%d", &n);
		for (int p=1;p<=n;p++) {
			for (int k=1;k<=n;k++) {
				book[p][k] = 0;
			}
		}
		for (int p=2;p<=n;p++) {
			for (int k=1;k<=(p+2)/4;k++) {
				char c;
				cin>>c;
				int u;
				if (c<='9') u = c-'0';
				else u = 10+c-'A';
				for (int i=0;i<=3;i++) {
					if ((u>>i)&1) book[p][4*k+i-3] = 1;
				}
			}
		}
		for (int p=1;p<=n;p++) {
			for (int k=1;k<p;k++) {
				if (!book[p][k]) book[k][p] = 1;
			}
		}
		for (int p=1;p<=n;p++) {
			int u = 0;
			for (int k=1;k<=n;k++) {
				if (book[p][k]) u++;
			}
			a[p] = {p, u};
		}
		stable_sort(a+1, a+n+1, cmp);
		for (int p=1;p<=n;p++) {
			place[a[p].i] = p;
			sum[p] = sum[p-1]+a[p].u;
		}
		for (int p=1;p<=n;p++) {
			sum[p]-=p*(p-1)/2;
			sum0[p] = sum0[p-1]+(sum[p]==0);
			sum1[p] = sum1[p-1]+(sum[p]==1);
			sum2[p] = sum2[p-1]+(sum[p]==-1);
		}
		for (int p=1;p<=n;p++) {
			int i = p;
			while (i<=n&&a[i].u==a[p].u) {
				i++;
			}
			i--;
			for (int k=p;k<=i;k++) {
				L[k] = p;
				R[k] = i;
			}
			p = i;
		}
		ll ans = 0, o = 1;
		for (int p=1;p<=n;p++) {
			for (int k=1;k<p;k++) {
				int i, j;
				if (!book[p][k]) i = L[place[k]], j = R[place[p]];
				else i = L[place[p]], j = R[place[k]];
				if (i==j+1&&a[i].u==a[j].u+1) ans = (ans+o*sum0[n])%mod;
				else if (i<j) ans = (ans+o*(sum0[n]-(sum0[j-1]-sum0[i-1])+(sum1[j-1]-sum1[i-1]))%mod)%mod;
				else ans = (ans+o*(sum0[n]-(sum0[i-1]-sum0[j-1])+(sum2[i-1]-sum2[j-1])));
				o = o*2%mod;
			}
		}
		printf("%lld\n", ans);
	}
	return 0;
}