Hazhir, The King of SBU Jungles!
"A chess game is divided into three stages: The first, when you hope you have the advantage, the second, when you believe you have an advantage, and the third… when you know you’re going to lose!"
Savielly Tartakower
King Hazhir is the king of SBU Jungles. His daughter is at SBG Jungles. King Hazhir received a letter telling that her daughter gave birth to a child. King is incredibly curious to see his grandchild! Unfortunately that's not so easy.
SBU and SBG are separated by a forest. There are lots of enemies in the forest, and King Hazhir is not that curious to see them. If they attack king on his way to SBG, then he will never ever see his grandchild and his daughter again because of lethal consequences.
King Hazhir has a security team: Amir, Amir Hossein, Navid and Koosha. If King Hazhir could not see his daughter and his grandchild, he will kill all members of his security team. Please help us, all of you dear newbie contestants!
The security team disposes information about location of the enemies, which makes the things easier for king Hazhir. For some unknown reason a forest is M×N chessboard. (M is the number of rows, and N is the number of columns). Enemies of the King can ride horses as showed in the picture. Usually horses ride (or jump) that way in Chess. The king moves the same way as chess-king does.
The enemies are fixed and can't move. King can't move to a square X, if a horse of the enemy is on that square or threat it, except for the case when square X is either kingdom SBU or SBG.
You're asked by the security team to find the length of the shortest route L from kingdom SBU to SBG, as dear king Hazhir can't wait any longer.
Input
The first line of input contains the number of tests T ≤ 100. The first line of each test contains 2 numbers M and N where N, M ≤ 100. Then M lines follow each containing N symbols from the set S = {'.', 'Z', 'U', 'G'}. '.' means that square is not occupied. 'Z' means a horse occupies that square. 'U' means kingdom SBU and 'G' means kingdom SBG. Each test contains exactly one kingdom SBU and SBG.
Output
Find number L for each test and print line "Minimal possible length of a trip is L." if King Hazhir can reach to the SBG. Replace "L" with corresponding number. If King Hazhir can't safely reach to the SBG print line "No King Hazhir, you can't go now! Don't kill us!"