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.
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 the answer of each test case on a separate line.
3 3 7 3942178 1234567 9123532 1 10 2H3HH4HHH5 4 4 3994 9999 9999 2924
5 4 -1