ADAPATH - Ada and Path


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 ≤ Aij < 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

hide comments
Arianto Wibowo: 2016-09-30 09:22:35

Thank you :)

morass: 2016-09-29 22:22:19

@Arianto Wibowo: Guess it is "600"

I increased timelimits. It didnẗ help much, yet if submited in "clang_cpp" it passed [so give it a try] :P

Last edit: 2016-09-29 22:36:18
Arianto Wibowo: 2016-09-29 21:43:40

what's the constraint of T?

morass: 2016-09-19 11:38:12

@[Rampage] Blue.Mary: Thank you so much man! Repaired!

[Rampage] Blue.Mary: 2016-09-19 03:58:53

There is an unnecessary 3 before the last example test case.


Added by:Morass
Date:2016-09-18
Time limit:4s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU