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.