Hazhir, The King of SBJ Jungles!#1466
King Hazhir is the king of the SBJ Jungles. His daughter is in the SBG Jungles. King Hazhir received a letter saying his daughter has given birth to a child. King Hazhir is very eager to see his grandchild, but unfortunately, that is not so easy.
SBJ and SBG are separated by a forest. There are many enemies in the forest, and King Hazhir does not want to encounter them. If they manage to attack the king on his way to SBG, all will end tragically, and the king will never see his daughter or grandchild.
King Hazhir also has his own security team: Amir, Amir Hossein, Navid, and Koosha. If King Hazhir cannot reach his daughter and grandchild, the members of the security team will also perish with him. Please help keep them all safe, dear contestants!
The security team knows the positions of the enemies, which makes your task and King Hazhir's journey easier. Some may find it odd, but the forest is shaped like an M \times N chessboard, where is the number of rows and is the number of columns. The king's enemies are mounted on horses and move like knights in chess. King Hazhir moves as a chess king does.
The enemies are stationary and cannot move. The king can step into a cell if it is not occupied or attacked by the enemies, except in the case where is the SBJ or SBG kingdom cell.
The security team asks for your help to find the length of the shortest path from SBJ to SBG, as King Hazhir cannot wait any longer.
The first line contains the number of tests (T \leq 100). The first line of each test contains numbers: and , where N, M \leq 100. The next lines each contain symbols from the set S = \{'.', 'Z', 'U', 'G'\}. '.' means an empty cell. 'Z' means a cell occupied by an enemy. 'U' is the SBJ kingdom, and 'G' is the SBG kingdom. Each test contains exactly one SBJ and one SBG kingdom cell.
For each test, print the length on a separate line in the format:
Minimal possible length of a trip is .
if King Hazhir can reach the SBG kingdom. Replace with the correct number. If King Hazhir cannot safely reach the SBG kingdom, print:
No King Hazhir, you can't go now! Don't kill us!
Example 1