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.