Still Johnny Can't Add

Interview

Time limit1sMemory limit128 MB

Summary

Decide whether an N by N grid can be written as row label plus column label for all cells, up to N=10.

Level: Medium4 of 10
Topics: Array, Math, Implementation, Matrix
Solved: No attempts yet

Problem

One way for young children in elementary school to practice addition is to have them fill in an addition table. An addition table of size $N$ is an $(N+1) \times (N+1)$ square matrix whose top row and left column are labeled with arbitrary integers (except for their intersection, the top-left cell, which normally holds a plus sign). Each remaining cell holds the sum of its row label and its column label.

For example, the following is an addition table of size 3. The bold entries are the labels; every interior cell equals the sum of its row label and column label (for instance, $1 + 3 = 4$ ).

+	3	-2	5
1	4	-1	6
4	7	2	9
-2	1	-4	3

Once the students grow up, we can pose the reverse question. Given an $N \times N$ grid that contains only interior values (no labels), decide whether labels can be assigned to the rows and columns so that every cell equals the sum of its row label and column label — that is, whether the grid could be the interior of a valid addition table. You do not need to produce the labels themselves; only decide whether such labels exist.

For example, the first $2 \times 2$ grid below is not the interior of any addition table, while the second one is.

The following grid is not an addition table:


1	4
3	5

The following grid is an addition table:


3	6
2	5

Input

The input begins with a line containing an integer $D$ , the number of test cases. Each test case begins with a line containing an integer $N$ ( $N \le 10$ ), the size of the table. The next $N$ lines each contain $N$ integers, giving the $N \times N$ table in row-major order. Every number in the table is between $-10000$ and $10000$ , inclusive.

Output

For each test case, print a single line in the format:

k. result

where $k$ is the test case number (starting at 1) and result is YES if the table is a valid addition table, or NO if it is not.

Examples4

Example 1

Input

Expected output

1. YES
2. NO
3. YES

Example 2
Input
```
1
2
0 3000
5000 8000
```
Expected output
```
1. YES
```
Example 3
Input
```
1
2
-10000 -5000
-8000 -3000
```
Expected output
```
1. YES
```

Example 4

Input

2
10
0 1 2 3 4 5 6 7 8 9
1 2 3 4 5 6 7 8 9 10
2 3 4 5 6 7 8 9 10 11
3 4 5 6 7 8 9 10 11 12
4 5 6 7 8 9 10 11 12 13
5 6 7 8 9 10 11 12 13 14
6 7 8 9 10 11 12 13 14 15
7 8 9 10 11 12 13 14 15 16
8 9 10 11 12 13 14 15 16 17
9 10 11 12 13 14 15 16 17 18
2
0 0
0 1

Expected output

1. YES
2. NO