#1351 Jumping Board

18  1 s   128 MB  

Description

You are given a rectangular board where each cell contains either an integer between 1 and 9, inclusive, or a hole.

Place a token into the cell in the upper left corner of the board. Now you can play a simple game. The game consists of moves, and each move looks as follows:

The game ends after a move that lands the token in a hole or outside the board. Your goal is to make as many moves as possible.

The board is given as an array of strings B. Characters '1' to '9' represent cells containing the corresponding integer, and letters 'H' represent holes. The upper left corner of the board corresponds to the first character of the first element of board.

Write a program that will compute the maximum number of moves you can make on the given board. If it is possible to make an arbitrarily large number of moves, your program should output -1.

 

 

Input

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

For each test case, two integers R and C (1 ≤ R, C ≤ 50) will be given, with R following lines.  Each of the following lines corresponds to each element of the array B.

 

 

Output

Output the answer of each test case on a separate line.

 

Sample Input

Sample Output

3
3 7
3942178
1234567
9123532
1 10
2H3HH4HHH5
4 4
3994
9999
9999
2924
5
4
-1