Ada the Ladybug loves Crosswords, Sudoku's and all other similar games. She has found an interesting game in the latest issue of Magazine Bug.

The game is simple - you will be given a square full of numbers. Each number must be part of exactly one path. Path must begin at number 1 and can only continue to neighboring number (left,right,up,down), which is larger by 1.

Ada's friend is working as a director of Magazine Bug. He wants to surprise her and add few more games to following issues of the magazine. Anyway, he wants you to check, whether the games are valid (i.e. if all the numbers can be part of a path).

Input

The first line will contain T, the number of test-cases.

Then T test-cases follow, each beginning with an integer 1 ≤ N ≤ 100, the size of the game board.

Afterward, N lines follow with N integers 1 ≤ A_ij < 10

Output

For each test-case print either "YES" if board is valid or "NO" if it isn't.

Example Input

4
4
1 2 3 4
4 3 2 1
1 2 2 1
1 1 1 2
3
1 2 3
4 5 6
1 2 1
2
1 2
4 3
2
1 2
2 2

Example Output

YES
NO
YES
NO