Given a duplicated maps like the ones shown below, you have to try to move ‘A’ and ‘B’ from the initial cell to the goal cell ‘E’ simultaneously. In these maps, you may travel through those free cell ‘.’, and may not move to the blocked cell ‘#’.
####### #######
#.....# #.....#
#.....# #.....#
#..E..# #..E..#
#.A...# #.B...#
#.....# #.....#
####### #######
However, there is a restriction that, whenever you try to move ‘A’ or ‘B’ a step to one of the adjacent cells in four directions, right, left, up and down, the other one must passively move a step to the adjacent cell in the opposite direction if possible. For example, if you move ‘A’ one step left, then ‘B’ must move one step right if the right cell is not a blocked cell. The following maps are the results after you move ‘A’ two steps up from the original position in the maps above.
####### #######
#.....# #.....#
#.A...# #.....#
#..E..# #..E..#
#.....# #.....#
#.....# #.B...#
####### #######
Note that in the second step, the cell that ‘B’ forced to move in is a blocked cell, so ‘B’ remains in the same position after ‘A’ moves up.
You have to find out the minimum number of steps to move ‘A’ and ‘B’ to the goal cell simultaneously, which means that ‘A’ and ‘B’ stay in the goal cell after a sequence of move. Note that moving one of them a step and forced the other one to move a step in the opposite direction is considered as a single step, instead of two. The starting cell and the goal cell are always considered as a free cell.
The first line of the input is an integer Z (Z ≤ 10), which means the number of test cases that follows.
For each test case, the first line contains two integers N and M (1 ≤ N, M ≤ 20), denoting the number of rows and columns of the maze. Each of the following N lines contains M characters representing the cells. The character ‘.’ means a free cell, ‘#’ means a blocked cell, ‘S’ means the starting cell of ‘A’ and ‘B’, and ‘E’ means the goal cell. There will be exactly one ‘S’ and ‘E’ in the maze, and you may safely assumed that the maze will be surrounded by the blocked cells.
There will be a leading blank line for each test case in the input.
For each test case, output a line containing the test case number (starting from 1) and the minimum number of steps to move ‘A’ and ‘B’ to the goal cell simultaneously. Output an integer -1 if it is impossible to achieve the goal. The detailed format is shown in the sample output, and note that there is a single space character before the sharp sign and after the colon.