In our programming course, our students have written programs that are supposed to solve the following problem: given an integer $n$ and an $n \times n$ table $$A = \begin{bmatrix} a_{11} & a_{12} & a_{13} & \dots & a_{1n} \\ a_{21} & a_{22} & a_{23} & \dots & a_{2n} \\ \dots \\ a_{n1} & a_{n2} & a_{n3} & \dots & a_{nn} \end{bmatrix},$$ they should construct an $n \times n$ table $$X = \begin{bmatrix} x_{11} & x_{12} & x_{13} & \dots & x_{1n} \\ x_{21} & x_{22} & x_{23} & \dots & x_{2n} \\ \dots \\ x_{n1} & x_{n2} & x_{n3} & \dots & x_{nn} \end{bmatrix}$$ such that $$x_{ij} = \sum_{k = 1}^n a_{ik} a_{jk} \bmod 64.$$ Put otherwise, element $(i,j)$ in table $X$ should be the dot product of rows $i$ and $j$ in table $A$, modulo 64.

Now your task is to quickly verify that the students have really solved the problem correctly. You will get $n$, table $A$, and table $X$, and you need to check if the solution is correct.

Input

The first line of input contains one integer, $t$, which is the number of test cases. Each case consists of:

• one line with integer $n$
• table $A$: $n$ lines with $n$ characters
• table $X$: $n$ lines with $n$ characters

The tables are encoded as strings as follows:

• each character corresponds to one element,
• characters A to Z correspond to values 0 to 25,
• characters a to z correspond to values 26 to 51,
• characters 0 to 9 correspond to values 52 to 61,
• character + corresponds to value 62,
• character / corresponds to value 63.

As everything is calculated modulo 64, we only need to store values 0–63.

Output

For each case, you will need to output one line: either 1 if $X$ is correct, or 0 if $X$ is not correct.

Limits

• $1 \le t \le 500$
• $1 \le n \le 5000$
• $0 \le a_{i,j} \le 63$
• $0 \le x_{i,j} \le 63$
• the sum of all $n$ values is at most 5000

Example

Input:

3
2
BC
DE
FL
LZ
2
BC
DE
FL
LF
4
m2ct
4k2u
MY0u
hrQW
BmeW
m48Y
e8kI
WYIe

Output:

1
0
1

Here we have three test cases ($t = 3$). In the first case we have $n=2$ and $$A = \begin{bmatrix} 1 & 2 \\ 3 & 4 \end{bmatrix}, \quad X = \begin{bmatrix} 5 & 11 \\ 11 & 25 \end{bmatrix}.$$Here all values are correct. For example, $1\cdot3 + 2\cdot4 = 11$. In the second test case the last element of $X$ is incorrect.