#1349 Collecting Riders

30  2 s   128 MB  

Description

A rider is a fantasy chess piece that can jump like a knight several times in a single move. (See hints section for a description of how a knight jumps.) A rider that can perform a maximum of K jumps during a single move is denoted as a K-rider. For example, a 2-rider can jump once or twice during a single move, and a 1-rider is a traditional knight.

There are some riders of different types on a chessboard. You are given a R*C matrix of characters named D, representing the layout of the pieces. If the character is a digit K between '1' and '9', the square contains a K-rider. Otherwise, if the character is a '.', the square is empty. Compute the minimal total number of moves necessary to move all the riders to the same square. Only one piece can move during each move. Multiple riders can share the same squares at all times during the process. Compute -1 if it is impossible.

Input

The first line contains the number of test cases T (T ≤ 100).

For each test case, two integers R and C (1 ≤ R, C ≤ 10) will be given, with R following lines.

Each of the following lines corresponds to row vector of the matrix D.

The matrix D will contain at least one digit.

Output

Output the answer of each test case on a separate line, or -1 if it is impossible.

Sample Input

Sample Output

2
3 4
...1
....
2...
8 8
........
.1......
........
....3...
........
........
.7......
........
2
2

HINT

A traditional knight has up to 8 moves from a square with coordinates (x,y) to squares (x+1,y+2), (x+1,y-2), (x+2,y+1), (x+2,y-1), (x-1,y+2), (x-1,y-2), (x-2,y+1), (x-2,y-1), and can not move outside the chessboard.