Божевільний Король
Король Петро живе в королівстві A, а його дочка в королівстві B. Король отримав листа, в якому повідомлялося, що його дочка народила дитину. Король неймовірно хоче побачити свого онука! На жаль, це буде не так просто.
Королівства A і B розділені лісом. У лісі багато ворогів, і король не прагне їх зустріти. Якщо вони нападуть на короля на шляху до королівства B, то він ніколи більше не побачить свого онука і дочку через летальні наслідки.
Таємна рада короля володіє інформацією про розташування ворогів, що полегшує завдання для короля. З невідомої причини ліс є M×N шахівницею. (M - це кількість рядків, а N - кількість стовпців). N, M ≤ 100 є додатними цілими числами.
Вороги короля можуть їздити на конях, як показано на малюнку. Зазвичай коні рухаються (або стрибають) так у шахах. На жаль, король не може взяти літак з точки A до точки B, тому що його ще не винайшли. Тому він рухається так само, як шаховий король (див. малюнок для деталей).
Король не може перейти на клітинку X, якщо на цій клітинці знаходиться кінь ворога. Поки король рухається, коні не рухаються, але якщо хоча б один кінь може досягти клітинки 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, виведіть рядок "Король Петро, зараз не можна йти!".