Problem Description

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

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

The input size of this problem is large, so fast input reading is recommended.

Input Format

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

Then there are $T$ test cases. In each test case, the first line contains a positive integer $n$, the matrix size.

The next $n$ lines each contain $n$ integers, describing matrix $A$.

The next $n$ lines each contain $n$ integers, describing matrix $B$.

The next $n$ lines each contain $n$ integers, describing matrix $C$.

Output Format

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

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

Yes
No
Yes

Hint

For $20\%$ of the testdata, $\sum n \le 300$.

For another $20\%$ of the testdata, the number of positions where $A_{i,j} \ne 0$ does not exceed $n$.

For $100\%$ of the testdata, $1 \le T, n \le 3000$, $\sum n \le 3000$, and $0 \le A_{i,j}, B_{i,j}, C_{i,j} < 998244353$.

Translated by ChatGPT 5