Judge correctness

• Time limit: 3.00 s
• Memory limit: 256 MB

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.