Description

The n-puzzle is a sliding puzzle that consists of a grid of numbered squares with one square missing, and the labels on the squares jumbled up. It is known in various versions, including 8 puzzle, 15 puzzle. If the grid is k*k, the puzzle is called k*k-1 puzzle. The goal of the puzzle is to un-jumble the squares by sliding squares horizontally or vertically to the empty square.

Figure 1: goal configuration of 15 puzzle

The n-puzzle is a classical problem for modeling algorithms involving heuristics. But, it is possible to show that some starting configurations are impossible to resolve, no matter how many moves are made. For example, it is impossible to change positions of 15 and 14 in the configuration shown in figure 2.
Figure 2: a starting configuration of 15 puzzle

Given the starting configuration of a n-puzzle, you are to tell whether it is possible to reach the goal configuration.

Input

There are multiple test cases. For each test case, an integer K (2 <= K <= 100) is given in the first line, which indicates a K * K grid; then the starting configuration is given in the following lines, 0 denotes the empty grid.

Output

For each test case, if the starting configuration is resolvable, print "YES" in a single line, otherwise, print "NO" instead.

Sample Input

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

Sample Output

YES
NO