Ravi a team member of Abhinav’s ACM ICPC team akatsuki11 is also a good friend of Abhinav. Ravi is a chess-freak who keeps on defeating Abhinav every time they play chess together. So Abhinav fed up of all this finally decides to seek revenge from his best friend. Being an excellent programmer Abhinav gives an interesting challenge to Ravi described below:

A Ghostrider is a fantasy chess piece created by Abhinav that can jump like a knight several times in a single move. A Ghostrider that can perform a maximum of X jumps during a single move is denoted as a X-Ghostrider. For example, 1-ghostrider is a traditional knight and a 3-ghostrider can jump once or twice or thrice during a single move.

There are some Ghostriders of different types on a chessboard. You are given an N x M board representing the layout of the pieces. The j-th character of the i-th row of the chess board is defined by the content of the square at row i, column j. If the character is a digit X between '1' and '9', then the square contains a X-ghostrider, else if the character is a '.', the square is empty. Now Abhinav wants Ravi to find the minimal total number of moves necessary to move all the ghostriders to the same square. Only one piece can move during each move and also multiple ghostriders can share the same squares at all times during the process. Return -1 if it is impossible move all the ghostriders to the same square.

Ravi is busy setting problems for the next epiphany. So it is now your job to solve the above challenge.

Note: -
1.) A knight has up to 8 moves from a square with coordinates (p,q) to squares (p+1,q+2), (p+2,q+1), (p+1,q-2), (p+2,q-1), (p-2,q+1), (p-1,q+2), (p-1,q-2), (p-2,q-1), and cannot move outside the chessboard (of course).
2.) The chessboard provided here is not a typical 8 x 8 chess board. It is an N X M chessboard.

Input:
First line contains number of test cases T.

For each test case:

First line contains two space separated integers N and M where N is the number of rows and M is the number of columns in the given chessboard.
Next N lines contain a sequence of characters containing digits between ‘1’-‘9’ or ‘.’.

Output:

If possible find the minimal total number of moves necessary to move all the ghostriders to the same square else print -1.

Constraints:

1 ≤ T ≤ 10

1 ≤ N ≤ 10

1 ≤ M ≤ 10

Explanation for Test Case 1 :

8 8

........

.1......

........

....3...

........

........

.7......

........SAMPLE INPUT
4
8 8
........
.1......
........
....3...
........
........
.7......
........
3 2
..
2.
..
1 8
.1....1.
10 10
9133632343
5286698232
8329333369
5425579782
4465864375
8192124686
3191624314
5198496853
1638163997
6457337215

SAMPLE OUTPUT
2
0
-1
121

见题面

见题面