Background

数字华容道是经典的滑块拼图游戏，通常包含一个 n∗n的棋盘（n>2），棋盘上有 (n*n−1)个标有不同数字（1至n∗n−1）的滑块，以及 1个空白位置（用 0表示）。玩家通过滑动滑块，将空白位置与相邻（上下左右）的滑块交换位置，最终目标是将所有滑块按数字从小到大的顺序排列（最后一行最右侧为空白位置，即 0的最终位置）。

现给定一个 (n∗n) 数字华容道的当前状态（ 以二维数组形式 ），请你编写程序判断该状态是否能通过有限次滑动，到达目标状态，即判断该华容道是否有解。

Input

开始时输入一个整数 t（t≤100），表示输入数据组数。 输入每组数据格式如下： 第一行输入一个整数 n（2≤n≤1000），表示棋盘的边长； 接下来 n 行，每行输入 n个整数，每个整数均为 0 至 (n*n−1)的不同整数，代表当前华容道的棋盘状态，其中 0表示空白位置；

Output

对于每组测试数据，若当前华容道状态有解，输出 YES；否则输出 NO，每组输出占一行。

Samples

2
3
1 2 3
4 6 0
7 5 8
3
1 2 3
4 5 6
8 7 0

YES
NO

sample1说明：
123  123  123  123
460->406->456->456
758  758  708  780