#include<bits/stdc++.h>

using namespace std;
typedef long long ll;

const int N = 5000 + 5, Mod = 1e9 + 7;
int n = 0, pw2[N * N] = {}, ans[N][N] = {}, E[N][N] = {}, ansx = 0;
int tot = 0, dfn[N] = {}, low[N] = {}, ok[N] = {}, col[N] = {}, scc = 0, sz[N] = {};
int sccx = 0, d[N] = {}, totx = 0, verx[N] = {}, colx[N] = {};
vector<int> ver;
vector<vector<int> > G(N);
stack<int> stk;
char s[N] = {};

inline void work(int c){
	int u = stk.top(); stk.pop();
	col[u] = c, sz[c] ++, ok[u] = 0;
}

inline void tarjan(int u){
	dfn[u] = low[u] = ++ tot;
	stk.push(u); ok[u] = 1;
	for(int v : G[u]){
		if(!dfn[v]){
			tarjan(v);
			low[u] = min(low[u], low[v]);
		}
		else if(ok[v]) low[u] = min(low[u], dfn[v]);
	}
	if(dfn[u] == low[u]){
		scc ++;
		while(stk.top() != u) work(scc);
		work(scc);
	}
}

inline bool cmp(int u, int v){
	return d[u] < d[v];
}

inline void initx(){
	for(int i = 0 ; i < totx ; i ++){
		colx[verx[i]] = 0;
		verx[i] = 0;
	}
	totx = sccx = 0;
}

inline void solvex(int x){
	for(int u = 1 ; u <= n ; u ++) if(col[x] == col[u] && u != x) verx[totx ++] = u;
	for(int u : G[x]) if(col[u] == col[x]) d[u] --;
	sort(verx, verx + totx, cmp);
	for(int i = 0, m = 0, k = 0 ; i < totx ; i ++){
		m ++, k += d[verx[i]];
		if(m * (m - 1) / 2 == k){
			for(int j = i ; j > i - m ; j --) colx[verx[j]] = sccx;
			m = k = 0, sccx ++;
		}
	}
	int y = 0, w = sccx;
	for(int u : G[x]) if(col[u] == col[x]){
		if(!colx[u] && !y) y = u;
		else w = min(w, colx[u]), ans[max(x, u)][min(x, u)] = scc;
		d[u] ++;
	}
	ans[max(x, y)][min(x, y)] = scc + w;
}

inline void init(){
	for(int u = 1 ; u <= n ; u ++) for(int v = 1 ; v <= n ; v ++) ans[u][v] = E[u][v] = 0;
	for(int u = 1 ; u <= n ; u ++){
		G[u].clear(), d[u] = 0;
		dfn[u] = low[u] = ok[u] = 0;
	}
	for(int c = 1 ; c <= scc ; c ++) sz[c] = 0;
	n = tot = scc = ansx = 0;
	stack<int>().swap(stk);
}

inline void solve(int cas){
	scanf("%d", &n);
	for(int i = 2 ; i <= n ; i ++){
		scanf("%s", s + 1);
		for(int k = 1 ; k <= (i + 2) / 4 ; k ++){
			int x = (s[k] >= '0' && s[k] <= '9') ? (s[k] - '0') : (s[k] - 'A' + 10);
			for(int j = 4 * k - 3 ; j <= 4 * k && j < i ; j ++){
				E[i][j] = (x >> (j - (4 * k - 3))) & 1;
				E[j][i] = E[i][j] ^ 1;
			}
		}
		if(cas == 2) printf("%s\n", s + 1);
	}
	for(int u = 1 ; u <= n ; u ++) for(int v = 1 ; v <= n ; v ++) if(E[u][v]) G[u].push_back(v);
	for(int u = 1 ; u <= n ; u ++) if(!dfn[u]) tarjan(u);
	for(int c = 1 ; c <= n ; c ++) if(sz[c] > 1){
		ver.clear();
		for(int u = 1 ; u <= n ; u ++) if(col[u] == c) ver.push_back(u);
		for(int u : ver) for(int v : ver) if(E[u][v]) d[v] ++;
		for(int u : ver) initx(), solvex(u);
	}
	for(int u = 1 ; u <= n ; u ++) for(int v : G[u]) if(col[u] != col[v]){
		if(col[u] - col[v] > 1 || sz[col[u]] > 1 || sz[col[v]] > 1) ans[max(u, v)][min(u, v)] = scc - (col[u] - col[v]);
		else ans[max(u, v)][min(u, v)] = scc;
	}
	for(int i = 1 ; i <= n ; i ++) for(int j = 1 ; j < i ; j ++) ansx = (ansx + 1ll * pw2[(i - 2) * (i - 1) / 2 + j - 1] * ans[i][j]) % Mod;
	//printf("%d\n", ansx);
}

int T = 0;

int main(){
	pw2[0] = 1;
	for(int i = 1 ; i < N * N ; i ++) pw2[i] = pw2[i - 1] * 2 % Mod;
	scanf("%d", &T);
	for(int i = 0 ; i < T ; i ++) init(), solve(i);
	return 0;
}