Сумасшедший король
Король Петр живет в королевстве A, а его дочь — в королевстве B. Король получил весть, что у его дочери родился ребенок, и теперь он мечтает увидеть своего внука. Однако это задача не из легких.
Королевства A и B разделяет лес, полный врагов, которых король предпочел бы избегать. Если враги нападут на короля по пути в королевство B, он может никогда больше не увидеть свою дочь и внука из-за смертельной опасности.
Тайный совет короля располагает сведениями о местонахождении врагов, что облегчает его задачу. По неизвестной причине лес имеет форму шахматной доски размером M×N (M — количество рядов, N — количество столбцов). N, M ≤ 100 — положительные целые числа.
Враги короля передвигаются на лошадях, как показано на рисунке. Обычно лошади ходят (или прыгают) так, как в шахматах. К сожалению, король не может воспользоваться самолетом, чтобы добраться из точки A в точку B, так как он еще не изобретен. Поэтому он передвигается так же, как шахматный король (см. рисунок для деталей).
Король не может ступить на клетку X, если на ней находится вражеская лошадь. Пока король движется, лошади остаются на месте, но если хотя бы одна лошадь может достичь клетки X за один ход, король не может туда переместиться (исключение составляют клетки, где находятся королевства A и B).
Вы — начальник отдела электронной разведки королевства A (кстати, компьютеры уже изобретены). Ваша задача — найти длину кратчайшего маршрута из королевства A в B, поскольку король очень хочет увидеть своего внука.
Входные данные
Первая строка ввода содержит количество тестов T ≤ 100. Первая строка каждого теста содержит 2 числа M и N. Далее следуют M строк, каждая из которых содержит N символов из множества S = {'.', 'Z', 'A', 'B'}. '.' обозначает свободную клетку. 'Z' обозначает клетку, занятую лошадью. 'A' — королевство A, 'B' — королевство B. Каждый тест содержит ровно одну клетку, обозначенную как королевство A, и одну клетку, обозначенную как королевство B.
Выходные данные
Для каждого теста найдите длину L кратчайшего маршрута и выведите строку "Минимальная возможная длина поездки — L", если король может добраться до королевства B. Если король не может безопасно добраться до королевства B, выведите строку "Король Петр, сейчас нельзя идти!".