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). 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}). For each test case, output the sum, modulo (10^9 + 7), of the values of all non-empty subsets of (S). 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$