Horrendous Maze

Time Limit: 10 Seconds Memory Limit: 65536 KB

There’s a simple but very interesting game called horrendous maze, which is like a regular maze with a few twists. The game is played on a N*M grid map, each grid is adjacent with 4 grids (up, down, left, right). There's only one exit on the map, the game finished when the player reaches the exit.

When the game starts, the player goes to the exit step by step. In each step he can only move to adjacent grid. But there's some barriers on the map, each barrier is either yellow or green. The player can not go to the grid when there is a barrier or an outside wall.

The only way to destroy the barriers is to stand on a grid which has a trigger. Each trigger is also yellow or green and can be used only once. When the player stands on it, it will send shock waves to destroy all the barriers with the same color it could reach directly. Shock waves spread as wide as possible in any direction. It can spread on all the connected grids where there’s no barrier on it, that means if it reach a barrier with different color, it will be blocked too. Notice if the wave can not reach a barrier directly, it cannot be destroyed, even if it's the same color with the trigger.

Now, not only we need to find out if a maze can be solved, we also want to know the minimum number of steps required to solve it.

Input

The first line of the input is an integer T < 16, indicating the number of test cases. For each case, the first line contains two integers N (1 ≤ N ≤ 40), M (1 ≤ M ≤ 40), N is the number of rows of the map, and M is the number of the columns.

The next N lines describe the map, each line has M characters. A character could be:

“.” means there's nothing, you can stand there.
“*”' means the outside wall, we guarantee that the outside wall form a close area and the player is in it.
“Y” means a yellow barrier, you can not stand there unless you have destroyed the barrier.
“G” means a green barrier, similar with “Y”.
“y” means a yellow trigger.
“g” means a green trigger. Notice the number of yellow trigger plus the number of green trigger is no more than 5.
“s” means the initial position of the player.
“e” means the exit, the player must go to there finally to finish the game.

There is a blank line between every two cases.

Output

Print one line for each test case: The minimal number of steps. If player can not reach the exit in any way, print “-1” instead.

Sample Input

1
5 17
*****************
*.......Y.......*
*.y.s...Y....e..*
*.......Y.......*
*****************

Sample Output

Submit