21797_BoardGame

Jerry developed a new board game recently. The board consists of N*N grids and M pieces have been randomly put in these grids. The game rules are defined as follows.

1. There is a unique grid defined as exit-grid.

2. In the initial state, no pieces is in exit-grid, and all the pieces are not adjacent to each other(in four directions: up, down, left, right).

3. All the M pieces are marked from 1 to M .

4. Each time you are allowed to move one piece to one of its adjacent blocks, which is counted as one step.

5. When you move the pieces, make sure that all the pieces are not adjacent to each other.

6. When the smallest piece, i.e. its marked number is the smallest on the board, is moved to exit-grid, you can take that piece away from the board. Pieces other than the smallest one are also allowed to move to exit-grid but they cannot be taken away.

7. When all the pieces on the board have been taken away, you win the game.

Tom is a very evil person. Every time Jerry playing the board game, he always says he has a better way to win the game, but he is not willing to tell Jerry. Jerry does not know whether Tom's words are true or not, so he asks for your help to write a program that can count the number of fewest steps to win the board game.

To simplify the problem, now we limit 2 ≤ N ≤ 6, 1 ≤ M ≤ 4 and all the initial states are correct.

The first line of the input contains a positive integer T ( T ≤ 200 ), which indicate the number of test cases.

Then follows T cases of inputs:

- a positive integer N

- a positive integer M

- an N*N matrix of characters to indicate the initial state of the board

If the element in the matrix is 'o', it means there is no piece in that grid; otherwise, the element is the marked number of that piece. Note that the element of exit-grid is 'x'.

For each test case, output one line with the number of fewest steps needed to win the game, or "-1" if it is impossible to accomplish that game.

2
3 2
x2o
ooo
oo1

3 3
xo1
o2o
3oo

7
-1