Problem J
Puzzling Plunder

Captain Crimson is known across the seven seas not just for the ruthlessness of his crew, but also for his genius. He and his crew search far and wide for the most prized treasures. No, not the ones with the most monetary value, silly! The ones safeguarded by the most challenging of puzzles! On one particular venture he finds himself faced with a chest with a most peculiar lock. Instead of a latch and keyhole he finds a rectangular panel of square numbered tiles! There is one missing tile to allow the tile above, below, to the left, or to the right to slide into the gap. He deduces that if he can rearrange the tiles into ascending order (right to left, top to bottom) with the one missing tile in the bottom right corner, then the lock will open. For example, the following puzzle can be solved in two moves as indicated.

After some time he solves the puzzle and sure enough the lock opens, and he gains access to the content of the chest. “What did he find?”, you may ask. What else but a map marking the locations of even more treasures! Captain Crimson begins his search for these treasures and after uncovering a few he realizes that all the chests are locked with similar puzzles to the first! In fact, they only differ in the dimensions of the puzzle. It is on his quest to find all the treasures that he encounters you. He explains that he has grown bored by these simple puzzles, but his crew insists of finding the rest for the easy profit. Can you create a program to quickly solve the puzzles so that Captain Crimson can continue on his search for more challenging puzzles?

Input

The first line will contain a single integer $1 \leq n \leq 50$ the number of puzzles to solve. For each of the $n$ puzzles, the first line will contain two integers $2 \leq h, w \leq 8$ the height and width of the puzzle respectively. The following $h$ lines will represent the puzzle, each containing $w$ integers numbered $0$ through $(h \cdot w) - 1$ ($0$ representing the missing tile). It is guaranteed that each puzzle is solvable in $20$ or fewer moves.

Output

For each of the $n$ puzzles, output a single line containing the minimum number of moves required to solve that puzzle.

4
2 2
1 2
0 3
3 3
1 2 3
4 0 6
7 5 8
3 3
1 0 5
4 8 2
7 6 3
8 8
0 2 3 4 5 6 7 8
1 10 11 12 13 14 15 16
9 18 19 20 21 22 23 24
17 26 27 28 29 30 31 32
25 34 35 36 37 38 39 40
33 42 43 44 45 46 47 48
41 50 51 52 53 54 55 56
49 57 58 59 60 61 62 63

1
2
9
14