#include <bits/stdc++.h>
#define rep(i,j,k) for(int i=(j);i<=(k);i++)
#define per(i,j,k) for(int i=(j);i>=(k);i--)
#define uint unsigned int
#define ll long long
#define ull unsigned long long
#define db double
#define ldb long double
#define pii pair<int,int>
#define pll pair<ll,ll>
#define mkp make_pair
#define eb emplace_back
#define SZ(S) (int)S.size()
//#define mod 998244353
#define mod 1000000007
#define inf 0x3f3f3f3f
#define linf 0x3f3f3f3f3f3f3f3f
using namespace std;

template <class T>
void chkmax(T &x,T y){
	if(x < y) x = y;
}

template <class T>
void chkmin(T &x,T y){
	if(x > y) x = y;
}

inline int popcnt(int x){
	return __builtin_popcount(x);
}

inline int ctz(int x){
	return __builtin_ctz(x);
}


ll power(ll p,int k = mod - 2){
	ll ans = 1;
	while(k){
		if(k % 2 == 1) ans = ans * p % mod;
		p = p * p % mod;
		k /= 2;	
	}
	return ans;
}
int T,n;
bitset <5005> G[5005];
int deg[5005];
char str[5005];

int getval(char ch){
	if('0' <= ch && ch <= '9') return ch - '0';
	return ch - 'A' + 10;
}

int k;
int p[5005],delta[5005],sum[2][5005];//恰好一次的,恰好没有的
ll P[2][5005];
ll getval(int u,int v){
	if(u < v) swap(u,v);
	return P[1][u] * P[0][v] % mod;
}

int q[5005];
int solve(int pos){
	int i = 1,j = pos + 1,kk = 0;
	while(i <= pos && j <= n){
		if(G[p[i]].test(p[j])) q[++kk] = p[i++];
		else q[++kk] = p[j++];
	}
	while(i <= pos) q[++kk] = p[i++];
	while(j <= n) q[++kk] = p[j++];
	int ans = 0,ssum = 0;
	for(i = 1;i <= n;i++){
		ssum += deg[q[i]];
		if(ssum == i * (i - 1) / 2) ans++;
	}
//	printf("(%d %d) %d\n",p[pos],p[pos + 1],ans);
	return ans;
}

void rev(int u,int v){
	if(G[u].test(v)){
		deg[v]--;
		deg[u]++;
		G[u].reset(v);
		G[v].set(u);
		return;	
	}
	//v -> u
	deg[u]--;
	deg[v]++;
	G[u].set(v);
	G[v].reset(u);
}

void solve(){
	scanf("%d",&n);
	rep(i,1,n){
		rep(j,1,n) G[i].reset(j);
		deg[i] = 0;
	}
	rep(i,1,n) P[1][i] = power(2,(i - 2) * (i - 1) / 2);
	rep(i,1,n) P[0][i] = power(2,i - 1);
	rep(i,2,n){
		scanf("%s",str + 1);
		rep(j,1,(i + 2) / 4){
			int v = getval(str[j]);
			if((v & 1) && 4 * j - 3 < i) G[i].set(4 * j - 3);
			if((v & 2) && 4 * j - 2 < i) G[i].set(4 * j - 2);
			if((v & 4) && 4 * j - 1 < i) G[i].set(4 * j - 1);
			if((v & 8) && 4 * j < i) G[i].set(4 * j);
		}
	}
	rep(i,1,n){
		rep(j,1,i - 1){
			if(!G[i].test(j)){
				G[j].set(i);
				deg[i]++;
			}else{
				deg[j]++;
			}
		}
	}

/*	rep(i,1,n){
		rep(j,1,n) printf("%d ",G[i].test(j));
		printf("\n");
	}*/

	k = 0;
	p[++k] = 1;
	rep(i,2,n){
		if(!G[p[1]].test(i)){
			per(j,k + 1,2) p[j] = p[j - 1];
			p[1] = i;
			k++;
			continue;
		}
		if(G[p[k]].test(i)){
			p[++k] = i;
			continue;
		}
		rep(j,1,k - 1){
			if(G[p[j]].test(i) && !G[p[j + 1]].test(i)){
				//插在 j+1 的位置
				per(s,k + 1,j + 2) p[s] = p[s - 1]; 
				p[j + 1] = i;
				++k;
				break;
			}
		}
	}
	rep(i,1,k - 1) assert(G[p[i]].test(p[i + 1]));
//	rep(i,1,k) printf("%d ",p[i]);
//	printf("\n");

	fill(delta + 1,delta + n + 1,0);
	rep(i,1,n){
		rep(j,i + 1,n){
			if(!G[p[i]].test(p[j])){
				delta[i]++;
				delta[j]--;
			}
		}
	}
	int ans = 1,res;
	rep(i,1,n - 1){
		delta[i] += delta[i - 1];
		sum[0][i] = sum[0][i - 1];
		sum[1][i] = sum[1][i - 1];
		if(!delta[i]){
			sum[0][i]++;
			ans++;
		}
		if(delta[i] == 1) sum[1][i]++;
	}
//	rep(i,1,n - 1) printf("[%d] %d %d %d\n",i,delta[i],sum[0][i],sum[1][i]);

	ll answer = 0;
	rep(i,1,n){
		rep(j,i + 2,n){
			if(G[p[i]].test(p[j])) res = ans - sum[0][j - 1] + sum[0][i - 1];
			else res = ans + sum[1][j - 1] - sum[1][i - 1];
//			printf("(%d %d) %d\n",p[i],p[j],res);
			answer += getval(p[i],p[j]) * res;
		}
		answer %= mod;
	}
	rep(i,1,n - 1){
		rev(p[i],p[i + 1]);
		answer += getval(p[i],p[i + 1]) * solve(i);
		rev(p[i],p[i + 1]);
	}
	answer %= mod;
	printf("%lld\n",answer);
}

int main(){
//	freopen("test.in","r",stdin);
//	freopen("test.out","w",stdout);
	scanf("%d",&T);
	while(T--) solve();
	return 0;
}