You are given three $n \times n$ matrices $A, B, C$ multiple times. You need to determine whether $A \times B$ is equal to $C$ modulo $998244353$.

Here, $\times$ denotes matrix multiplication, where $C_{i,j} = \sum_{k=1}^{n} A_{i,k} B_{k,j}$.

The input size for this problem is large; it is recommended to use fast I/O.

Input

The first line contains a positive integer $T$, representing the number of test cases.

The input then contains $T$ test cases. For each test case, the first line is a positive integer $n$, representing the size of the matrices.

The next $n$ lines, each containing $n$ integers, represent matrix $A$.

The next $n$ lines, each containing $n$ integers, represent matrix $B$.

The next $n$ lines, each containing $n$ integers, represent matrix $C$.

Output

Output $T$ lines, each containing either "Yes" or "No", indicating whether $A \times B$ is equal to $C$ modulo $998244353$.

Constraints

• For 20% of the data, $\sum n \le 300$.
• For another 20% of the data, the number of positions where $A_{i,j} \neq 0$ does not exceed $n$.
• For 100% of the data, $1 \le T, n \le 3000$, $\sum n \le 3000$, and $0 \le A_{i,j}, B_{i,j}, C_{i,j} < 998244353$.

Examples

Input 1

3
1
2
3
6
2
1 2
3 4
5 6
7 8
19 22
43 51
2
1111111 2222222
3333333 4444444
5555555 6666666
7777777 8888888
39625305 256038638
772687616 944903942

Output 1

Yes
No
Yes