Almost Acyclic

We call a connected undirected graph almost-acyclic, if the graph has no cycles, or all the simple cycles in it share at least one common point.

You are given a complete undirected graph $G=(V,E)$ with $n$ vertices. Each edge $(i,j)$ has a weight $w_{i,j}$. Calculate ($f(G)$ is $1$ if $G$ is almost-acyclic, or $0$ otherwise):

$$\sum_{E'\subseteq E,\: G'=(V,E')} f(G') \prod_{(i,j) \in E'} w_{i,j} \bmod 10^9+7 $$

Input

The first line contains a single integer $T \: (1\leq T \leq 16)$, denoting the number of test cases.

For each test case, the first line contains an integer $n \: (1\leq n \leq 16)$.

The next $n$ lines each contains $n$ integers. The $j$-th number in the $i$-th line denotes $w_{i,j} \: (0 \leq w_{i,j} < 10^9+7)$ .

It is guaranteed that $w_{i,j} \: = w_{j,i}$, $w_{i,i} = 0$.

It is guaranteed that for each $1 \leq i \leq 16$, there is at most one test case satisfying $n = i$.

Output

For each test case, output one line with an integer denoting the answer.

Example

2
3
0 1 2
1 0 1
2 1 0
5
0 1 0 1 1
1 0 1 1 1
0 1 0 1 0
1 1 1 0 1
1 1 0 1 0

7
120