Untitled

In the secret mountain cave, young hobbit Frodo gets information about the existence of Nenya, the ring of water and he finds a map with its location. But on his way to the ring, Frodo encounters a maze. Now this is no ordinary maze. The maze is in the form of a rectangle with n rows and m columns. Each cell of the maze is a room and a room in the ith row and jth column is addressed as room(i,j). Rows are numbered from 1 to n from top to bottom and columns are numbered from 1 to m from left to right.

The maze has two types of rooms: type A and type B. In each room of type A, there is a monster who is very hungry and Frodo must give him an apple otherwise the monster will eat him. The room also contains one gold coin. In each room of type B, there is a guard who is very greedy and Frodo must give him a gold coin otherwise the guard will kill him. The room also contains an apple.

Every room has a door to every adjacent room (Rooms that share an edge are adjacent rooms). Before entering the maze Frodo has the choice of taking either a gold coin or an apple. Frodo enters the maze from room(1,1) and he has to reach the room(n,m) to get out of the maze. Frodo does not have much time. Tell Frodo the minimum number of rooms he needs to visit to get out of the maze alive.

Input
The first line of the input contains an integer T denoting the number of test cases. First line of each test case consists of two integers n and m.Then follows n lines with m characters each describing the maze. '0' for room of type A and '1' for room of type B.

Output
For every test case print the minimum number of rooms Frodo needs to visit to get out of the maze. If it is not possible to cross the maze, print "-1" without the quotes.
Note: print output in the format shown in the sample below '#testcase answer'

Constraints
1 ≤ T ≤ 10
1 ≤ n ≤ 1000
1 ≤ m ≤ 1000
 

Example
Input:
2
3 3
0 1 1
0 0 1
0 0 0
2 2
1 1
0 0

Output:
#1 5
#2 -1

10
3 3
0 1 1 
0 0 1 
0 0 0 
2 2
1 1 
0 0 
3 5
0 0 0 1 0 
1 0 1 0 1 
1 0 1 1 0 
9 9
0 1 0 1 1 1 1 1 0 
0 1 0 0 1 1 1 1 1 
1 0 0 1 1 0 1 1 1 
0 1 0 0 0 0 1 1 1 
1 1 0 1 1 0 1 1 1 
0 0 1 0 0 1 0 1 1 
0 1 1 0 1 0 0 0 0 
0 0 0 1 0 0 0 1 1 
1 1 0 0 1 1 1 0 1 
16 12
0 0 1 1 1 1 1 0 1 1 1 1 
1 0 0 0 0 0 1 1 1 1 1 0 
0 0 0 1 1 0 0 0 0 0 0 0 
1 0 1 1 0 0 1 0 1 0 0 0 
1 1 0 1 1 0 0 0 0 0 1 0 
1 1 1 0 0 1 0 0 1 1 1 0 
0 0 1 1 0 1 0 1 0 1 1 1 
1 0 0 0 1 1 1 1 1 1 0 1 
1 0 1 0 0 1 0 1 1 0 1 1 
0 1 0 0 1 1 1 1 1 1 0 0 
0 1 0 1 1 0 1 0 1 1 1 1 
1 0 1 0 1 0 1 0 0 1 1 0 
0 1 0 0 0 0 0 1 1 0 0 1 
1 0 1 1 0 1 1 0 1 1 1 1 
0 0 1 0 1 0 1 0 0 1 0 1 
1 1 1 1 0 0 0 0 1 1 1 0 
20 20
0 0 1 0 0 0 0 1 1 1 0 1 0 0 0 0 0 1 0 0 
1 0 1 0 0 1 1 0 1 1 0 1 1 1 0 1 0 1 0 1 
1 1 0 1 0 0 1 1 1 0 0 1 0 1 0 1 1 0 0 1 
0 0 0 0 0 0 1 1 0 0 1 0 1 1 1 1 1 0 1 1 
1 0 1 1 0 0 1 0 0 0 1 0 1 1 1 1 0 1 1 1 
1 0 1 1 1 0 1 1 1 0 1 1 1 1 0 0 0 0 1 0 
0 0 1 0 1 0 0 0 0 0 1 0 1 1 0 1 0 0 1 0 
0 0 1 0 1 1 1 1 1 1 1 0 0 0 0 0 0 1 1 0 
0 1 0 1 1 1 0 0 1 1 1 0 1 0 1 1 1 0 0 0 
1 1 1 1 0 0 0 1 0 1 1 1 1 0 1 0 0 0 1 1 
1 1 1 1 1 1 0 1 0 0 0 0 1 0 1 0 1 1 0 0 
0 0 0 0 0 1 1 0 0 0 1 0 0 1 0 0 0 1 0 1 
1 0 1 0 0 0 0 0 0 0 0 0 1 1 0 0 1 0 1 1 
0 1 1 1 1 1 1 0 1 0 1 0 1 0 1 0 0 0 1 0 
1 1 0 1 1 1 0 0 1 0 0 1 1 1 0 1 1 0 0 0 
1 0 0 0 0 1 1 1 0 1 1 1 1 1 1 0 1 0 0 1 
1 1 0 1 1 1 1 1 0 0 1 1 0 1 0 0 0 0 1 1 
0 1 0 1 1 0 1 1 0 0 0 0 1 1 1 0 1 1 0 0 
1 0 0 1 1 1 1 1 1 1 1 1 1 1 0 1 1 0 1 0 
0 0 1 0 1 0 0 1 0 1 1 1 0 0 1 0 1 0 1 0 
30 20
1 0 0 1 1 0 0 0 0 1 1 1 0 1 1 0 0 0 1 0 
1 1 0 0 1 1 1 1 0 0 0 1 1 0 1 1 1 1 0 1 
0 0 1 0 0 0 1 0 0 1 0 1 1 0 1 1 0 1 0 0 
0 0 0 0 0 1 0 1 0 1 1 1 0 0 1 0 1 0 0 0 
1 1 1 1 1 0 1 0 1 0 1 0 0 1 1 1 1 1 0 0 
0 1 0 1 0 0 0 0 1 0 1 1 0 1 1 1 1 1 1 0 
0 0 1 1 0 1 0 0 1 1 1 1 1 1 1 0 0 1 1 1 
0 1 0 1 0 1 0 1 1 1 0 0 1 1 0 1 0 1 1 1 
0 1 0 1 1 1 1 0 1 1 1 0 0 0 0 1 0 1 1 0 
0 1 1 0 1 1 1 0 0 1 1 0 0 0 1 0 1 0 1 1 
1 0 0 1 1 0 0 0 1 0 1 1 1 1 0 1 0 0 1 0 
1 1 0 1 0 0 1 1 1 1 0 0 1 1 1 0 1 0 0 0 
1 0 0 0 0 1 0 1 0 0 1 1 0 0 1 0 0 1 0 1 
0 0 1 0 0 0 0 0 1 1 1 0 1 1 1 0 0 0 0 1 
1 0 0 1 1 0 0 0 1 0 1 0 1 1 1 1 1 1 0 0 
1 0 1 1 0 0 0 0 1 1 1 0 1 1 0 1 1 1 1 0 
1 1 1 1 0 1 1 0 1 0 1 0 1 0 1 1 0 1 0 0 
1 0 1 0 0 1 0 0 0 0 0 1 1 0 1 0 0 0 1 0 
0 0 0 1 1 1 1 0 0 1 1 0 0 1 0 0 0 0 0 1 
0 1 0 1 1 0 0 0 0 0 0 1 1 0 0 0 1 1 0 1 
0 0 0 1 0 0 0 0 0 1 1 0 1 0 1 0 1 0 0 0 
1 1 0 1 1 0 1 1 1 1 1 1 0 0 0 0 1 1 1 1 
0 0 1 1 0 0 1 1 1 1 0 0 0 0 1 1 0 0 0 1 
1 1 1 1 1 0 0 0 1 1 0 0 0 1 1 1 1 1 0 1 
1 1 1 0 1 1 0 0 1 0 1 1 0 1 1 0 1 0 1 1 
1 1 1 1 0 0 0 1 1 0 1 1 0 0 0 1 1 0 0 1 
0 1 1 1 0 0 1 0 1 1 1 1 1 1 1 1 0 0 1 1 
0 1 0 1 0 0 0 1 0 1 1 1 1 1 0 1 1 0 0 1 
1 1 1 0 0 1 0 1 0 0 1 0 1 0 1 0 0 1 0 0 
0 0 1 0 0 0 1 0 1 0 0 0 0 0 0 0 1 0 0 1 


#1 5
#2 -1
#3 7
#4 -1
#5 29
#6 41
#7 49
#8 -1
#9 -1
#10 1999