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

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

- 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.

**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.