Little K has a tournament graph with $n$ vertices, labeled $1$ to $n$. As is well known, a tournament graph is a directed graph where for every $1 \le i < j \le n$, exactly one of the directed edges $i \to j$ or $j \to i$ exists.

Little K is taking an online course, and one of the assignments is to transfer this tournament graph to another computer. However, signal interference occurred during the transfer, resulting in exactly one edge being reversed in the new graph. Little K quickly solved this problem. But Little K is curious: for the given tournament graph, if the direction of the edge connecting $i$ and $j$ is reversed for every $1 \le i < j \le n$, how many maximal strongly connected components does the new tournament graph have?

Input

The first line contains an integer $T$ ($1 \le T \le 10\,000$), the number of test cases.

For each test case:

The first line contains an integer $n$ ($1 \le n \le 5000$), the number of vertices.

The next $n-1$ lines, where the $i$-th line is a string of length $\left\lceil\frac i4\right\rceil$, where the $j$-th character is the hexadecimal digit corresponding to $\sum_{k=0}^3 2^k E_{i+1, 4j+k-3}$ (where $10 \sim 15$ correspond to uppercase letters $\texttt A \sim \texttt F$), and $E_{i,j}=1$ if and only if $j < i$ and the edge between $i$ and $j$ is directed from $i$ to $j$.

It is guaranteed that there is at most one test case with $n > 10$.

Output

For each test case, output a single line containing the value of $\sum_{i=1}^n \sum_{j=1}^{i-1} 2^{(i-2)(i-1)/2+j-1} ans_{i,j}$ modulo $10^9+7$, where $ans_{i,j}$ is the number of maximal strongly connected components in the tournament graph obtained after reversing the edge between $i$ and $j$.

Examples

Input 1

2
3
0
2
6
1
3
7
F
F1

Output 1

19
153406

Note 1

In the first test case, there are $3$ vertices with the edge set $\{(1, 2), (1, 3), (3, 2)\}$. We have $ans_{1,2} = 1$, $ans_{1,3} = ans_{2,3} = 3$.

Constraints

For all test cases, $T \le 10\,000$, $1 \le n \le 5000$.

Subtask 1 ($20\%$): $n \le 100$;

Subtask 2 ($20\%$): $n \le 300$;

Subtask 3 ($20\%$): $n \le 500$;

Subtask 4 ($20\%$): $n \le 1500$;

Subtask 5 ($20\%$): $n \le 5000$.