Crazy King

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

Kingdoms A and B are separated by a forest. There are lots of enemies in the forest, and the 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.

Security Council of the king disposes information about the location of the enemies, which makes 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, 1 ≤ M, N ≤ 100.)

The enemies of the king can ride horses as shown in the picture below. Usually, horses ride (or jump) the same way as in chess. Unfortunately, the king can't take an airplane from point A to point B, because it is not invented yet. So he moves the same way as a chess-king does (refer to the picture for details).

The king can't 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 can't move to that square (except for the case when square X is either kingdom A or B).

You are the chief of Electronic Intelligence department of kingdom A (by the way, computers are already invented), and you're asked to find the length L of the shortest route from kingdom A to B, as the king can't wait any longer.

Input Specification

The first line of the input contains the number of test cases T (T ≤ 100). The first line of each test case contains two numbers M and N. Then M lines follow, each containing N symbols from the set S = {“.”, “Z”, “A”, “B”}. “.” means that the square is not occupied. “Z” means that a horse occupies that square. “A” denotes kingdom A, and “B” denotes kingdom B. Each test case contains exactly one kingdom A and one kingdom B.

Output Specification

Find number L for each test case, and print a line containing “Minimal possible length of a trip is L” if the king can reach kingdom B. Replace “L” with the corresponding number. If the king can't safely reach kingdom B, print a line containing “King Peter, you can't go now!”.

Sample Input

1. 4
2. 5 5
3. .Z..B
4. ..Z..
5. Z...Z
6. .Z...
7. A....
8. 3 2
9. ZB
10. .Z
11. AZ
12. 6 5
13. ....B
14. .....
15. .....
16. ..Z..
17. .....
18. A..Z.
19. 3 3
20. ZZ.
21. ...
22. AB.

download as text file

Output for Sample Input

1. King Peter, you can't go now!
2. Minimal possible length of a trip is 2
3. King Peter, you can't go now!
4. Minimal possible length of a trip is 1

download as text file