A :: Jumping Hero

Time Limit: 5 Seconds Memory Limit: 32768 KB

A software house has decided to create a computer game, where the hero must find its way from a start position to the end position, through a labyrinth. In the labyrinth, some cells contain magic fountains that can be used to get super-powers an infinite number of times. Whenever the hero enters a cell with a magic fountain, he gets super-powers.

Usually, our hero moves in the labyrinth one cell left/right/up/down at a time (to an empty cell). With super-powers, the hero jumps to an empty cell N positions to the left/right/up/down. The super-power lasts for M jumps, and the hero can change its jumping direction after each jump. A jump is allowed if the end cell of the jump is within the map and it is not a wall,thus, the hero can jump over walls. If the hero jumps to a cell with a new magic fountain, the hero gets the super-powers of the new magic fountain, and the remaining effect of the previous magic fountain is cancelled. If the hero jumps to the cell where he obtained its current super-powers, no effect occurs (i.e., the hero gets no additional super-powers). When the current super-power ends, the hero proceeds its normal one-cell movement. If, after getting super-powers in some fountain, the hero cannot move to any cell, he looses his super-powers and returns to his previous cell. To reach the end position, the hero must move to the end cell or finish one jump in the end cell.

Given the labyrinth map compute the minimum number of moves/jumps from the start position to the end position.

Input

A positive integer P in a single line followed by a sequence of P labyrinth maps. The first line of each labyrinth map contains two positive integers, L and C, separated by an empty space, with L the number of lines and C the number of columns in the map. L and C are both lesser than 300. The following L lines of the input contain C integers each that define the cells of the map (separated by a empty space). Each integer, i, must be interpreted as follows: i = 0 represents a wall; i = 1 represents an empty cell (where the hero can move into); i = M*10+N represents an empty cell with a magic fountain that makes the hero jump M times to the cell that is N positions to the left/right/up/down of the current cell. M ranges from 1 to 5 and N ranges from 2 to 6. The maximum number of magic fountains in a map is 5,000. The two last lines of the input define the coordinates of the start position and end position (coordinates consist of two integers, denoting the line and column respectively, starting from 0).

Output

The output consists of one single line that contains an integer with the minimum number of moves/jumps, from the start position to the end position. If it is impossible to reach the end position, the output should be a single line containing IMPOSSIBLE.

Sample Input

1
8 8
0  1  1  1  1  1  1  1
0  1  0  0  1  13 1  1
0  1  32 1  1  1  0  0
0  1  1  0  1  1  1  0
0  1  1  0  0  0  0  0
0  1  1  1  1  1  1  0
0  1  0  0  1  1  1  0
0  1  1  1  1  1  1  0
1 7
5 4

Sample Output

Submit