"Хід шахової партії можна розділити на три этапи: перший, коли Ви думаєте, як отримати перевагу, другий, коли Ви вважаєте, що отримали перевагу, і третій... - коли Ви знаєте, що вже програли!"
Савелій Тартаковер
Король Хазхір - це король джунглів СБУ. Його дочка знаходиться у джунглях СБГ. Король Хазхір отримав листа, у якому повідомляється, що його донька народила дитину. Королю дуже хочеться побачити свого онука, але, на жаль, це не так просто.
СБУ та СБГ відокремлені лісом. У лісі є багато ворогів і королю Хазхіру не хочеться з ними зустрічатись. Якщо вони зуміють атакувати короля по його дорозі у СБГ, все завершиться летальным результатом і, звичайно, король ніколи не побачить свою доньку і онука.
У короля Хазкіра є і своя служба безпеки: Амір, Амір Хусейн, Навід та Куша. Якщо король Хазхір не зуміє побачити свою доньку та онука, то разом з ним загинуть і члени його служби безпекти. Будь-ласка, допоможіть їм всім залишитись живими, шановні учасники контесту!
Команда безпеки володіє інформацією про місцезнаходження ворогів, що полегшує Ваше завдання і життя короля Хазхіра. Комусь це може здатись дивним, але ліс має вид шахової дошки розміром M×N (M - це кількість рядків, а N - кількість стовбчиків). Вороги короля знаходяться на конях і переміщуються вони стрибками точно так само, як ходить кінь у справжніх шахах. Король СБУ може переміщуватсь точно так само, як це робить шаховий король..
Вороги є нерухомими. Король може заходити у довільну клітинку леса X, якщо вона не зайнята ворогами, або не знаходиться під прицілом ворогів, за винятком того випадку, коли клітинка X є королівським домом СБУ чи СБГ.
Служба безпекти попросила Вашої допомоги знайти довжину L найкоротшого шляху від СБУ до СБГ, так як король Хазхір вже не може більше чекати.
Перший рядок містить кількість тестів T ≤ 100. Перший рядок кожного тесту містить 2 числа M і N, де N, M ≤ 100. Наступні M рядків містять кожен по N символів множини S = {'.', 'Z', 'U', 'G'}. '.' позначено вільні клітинки. 'Z' позначає клітинку, зайняту ворогами. 'U' позначає королівський будинок СБУ і 'G' позначає королівський будинок СБГ. У всіх тестах міститься по одному королівському будинку СБУ і СБГ.
Виведіть довжину L для кожного тесту у окремому рядку і вигляді "Minimal possible length of a trip is L." якщо король Хазхір зможе дістатись до СБГ. Відповідно, значення "L" повинно бути замінено відповідним числовим значення. Якщо король Хазхір не зможе дістатись безпечно до СБГ, виведіть у відповіному рядку повідомлення "No King Hazhir, you can't go now! Don't kill us!"