In 8-Puzzle, you are given a square frame puzzle which consists of 8 numbered tiles and one missing tile. By shifting the tiles to the empty tile position, you are asked to put the numbers in proper order. Your professor is developing a program to solve this problem automatically. For this, he wants a program which solves kth puzzle problem for k between 3 and 7. But solving big puzzles takes too much time so he decided to limit the search process. For that, he wants to search at most 15 steps to decide when k is 3 or 4, and at most 12 steps when 5 ≤ k ≤ 7.

Question: Write a program that reads a matrix configuration. And then, it finds if there is a solution within the given steps length.

Input specification
In the first line, you will be given an integer (n) where 3 ≤ n ≤ 7. Then, in the following n lines you will be given n integers where each number is between 0 and n²-1 And, zero (0) represents the position of the empty tile.

Output specification
If there is a solution show the number of minimum steps. Show -1 (minus 1), if there is no solution within the defined limits (max number of steps given).

Explanation First, you move 8 to the position of 0, then 7 and 4 are moved down, etc.