eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Crazy King

Crazy King

Лимит времени 1 секунда
Лимит использования памяти 64 MiB

King Peter lives in kingdom A, and his daughter in kingdom B. The king recieved a letter saying that her daughter gave birth to a child. The king is incredibly curious to see his grandchild! Unfortunately that's not going to be easy.

Kingdoms A and B are separated by a forest. There are lots of enemies in the forest, and King is not that curious to see them. If they attack the king on his way to kingdom B, then he will never ever see his grandchild and daughter again because of lethal consequences.

The Privy Council of the King possesses information about location of the enemies, which makes the things easier for the king. For some unknown reason the forest is an M×N chessboard. (M is the number of rows, and N is the number of columns). N, M100 are positive integers.

Enemies of the King can ride horses as shown in the picture. Usually horses ride (or jump) that way in Chess. Unfortunately king cannot take an airplane from point A to point B because it is not invented yet. So he moves the same way as chess-king does (refer to picture for details).

The king cannot move to a square X if a horse of the enemy is on that square. While the king is moving, horses are not, but if at least one horse can reach square X in one move, then the king cannot move to that square (except for the case when square X is either kingdom A or B).

You are the chief of the Electronic Intelligence dapartment of kingdom A (by the way the computers are already invented). And you're asked to find the length of the shortest route from kingdom A to B, as the king is very anxious to see his grandchild.

Входные данные

The first line of input contains the number of tests T100. The first line of each test contains 2 numbers M and N. Then M lines follow each containing N symbols from the set S = {'.', 'Z', 'A', 'B'}. '.' means that square is not occupied. 'Z' means a horse occupies that square. 'A' - kingdom A, 'B' - kingdom B. Each test contains exactly one square labelled kingdom A and one square labelled kingdom B.

Выходные данные

Find the length L of the shortest route for each test and print a line "Minimal possible length of a trip is L" if the king can reach kingdom B. If the king cannot safely reach the kingdom B print line "King Peter, you can't go now!".

Пример

Входные данные #1
4
5 5
.Z..B
..Z..
Z...Z
.Z...
A....
3 2
ZB
.Z
AZ
6 5
....B
.....
.....
..Z..
.....
A..Z.
3 3
ZZ.
...
AB.
Выходные данные #1
King Peter, you can't go now!
Minimal possible length of a trip is 2
King Peter, you can't go now!
Minimal possible length of a trip is 1