- 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
toZ
correspond to values 0 to 25, - characters
a
toz
correspond to values 26 to 51, - characters
0
to9
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.