Code Submission Evaluation System Login

HIIT Open 2016

Start:2016-05-28 11:00:00
End:2016-05-28 16:00:00
 

Tasks | Messages | Scoreboard | Statistics


CSES - HIIT Open 2016 - Judge correctness

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: The tables are encoded as strings as follows: 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
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.