In a two-dimensional universe, a star can be represented by a point $(x,y)$ on a two-dimensional plane. Two stars are directly connected if and only if their $x$ or $y$ coordinates are the same, and there are no other stars on the line segment between them. Define a galaxy as a connected component composed of stars connected directly or indirectly (through other stars).

For a set of stars, its value is defined as the minimum number of galaxies that can be obtained after performing the following operation for any (possibly, zero) times: in each operation, you can select a point $(x,y)$ without stars. If a star can be directly connected to at least $3$ stars after creating it here, then you create a star here.

You are given a $n\times n$ matrix $a$ consisting of $0$ and $1$ describing a set $S$ of stars. There is a star at $(x,y)$ if and only if $a_{x,y}=1$. Calculate the sum, modulo $10^9 + 7$, of the values of all non-empty subsets of $S$.

Input

The first line of input contains a single integer $t$ ($1 \leq t \leq 100$) — the number of test cases.

For each test case, the first line contains a single integer $n$ ($1 \leq n \leq 14$) — the size of matrix $a$.

Then $n$ lines follow; the $i$-th line contains a string $a_i$ of length $n$ — the $i$-th row of matrix $a$.

It is guaranteed that the sum of $2^n$ over all test cases does not exceed $2^{14}$.

Output

For each test case, output the sum, modulo $10^9 + 7$, of the values of all non-empty subsets of $S$.

见题面 Input 部分

见题面 Output 部分

In the first test case, $S$ is empty. $S$ has no non-empty subsets. So the answer is $0$.

In the second test case, $S = \{(1,2),(2,1)\}$. $S$ has $3$ non-empty subsets.

• $\{(1,2)\}$ and $\{(2,1)\}$ — there is only one star in the set, forming $1$ galaxy.
• $\{(1,2),(2,1)\}$ — two stars in the set are not connected, forming $2$ galaxies.

So the answer is $1+1+2=4$.

In the third test case, $S = \{(1,2),(3,1),(3,3)\}$. $S$ has $7$ non-empty subsets.

• $\{(1,2)\}$, $\{(3,1)\}$, and $\{(3,3)\}$ — there is only one star in the set, forming $1$ galaxy.
• $\{(1,2),(3,1)\}$ and $\{(1,2),(3,3)\}$ — two stars in the set are not connected, forming $2$ galaxies.
• $\{(3,1),(3,3)\}$ — two stars in the set are connected, forming $1$ galaxy.
• $\{(1,2),(3,1),(3,3)\}$ — initially, star $(1,2)$ is not in the galaxy formed by $(3,1)$ and $(3,3)$. You can make an operation creating a star at $(3,2)$ connecting to these three stars, forming $1$ galaxy.

So the answer is $1+1+1+2+2+1+1=9$.