Король
Аліса та Боб грають у гру. Гра проходить на дошці, що містить R рядків та C стовбців, загалом з R×C клітинок. Деякі з цих клітинок спалено.
Короля розміщено у одній із незгорівших клітинок, а Аліса та Боб по черзі роблять ходи королем.
За один хід гравець повинен перемістити короля у довільну з його 8 сусідніх клітинок, дотримуючись при цьому наступних двох умов:
Клітинка призначення не повинна бути спаленою.
Король ніколи не повинен бути переміщеним у клітинку, у які вже до цього побував.
Якщо гравець не може зробити хід, він чи вона програє. Першою хід робить Аіиса, а ви повинні визначити, хто виграє, припускаючи, що обидва гравці грають оптимально.
Вхідні дані
У першому рядку вхідних даних задано кількість наступних тестових прикладів N (1 ≤ N ≤ 100).
Далі йдуть самі N тестових прикладів. Перший рядок у кожному тестовому випадку буде складатись з двох цілих чисел, R та C (1 ≤ R , C ≤ 15 ). Наступні R рядків будуть містити рядки довжиною C, які задають C клітинок кожного рядка. Кажен рядок буде містити лише символи ".", "#" та "K":
"#"позначає спалену клітинку;
"." позначає, що клітинка не сгоріла і не зайнята;
"K"позначає клітинку, у якій знаходиться король на початку гри.
Гарантується, що буде лише одна клітинка, яка містить "К" у кожному з тестів.
Вихідні дані
Для кожного тесту виведіть один рядок, який містить "Case # X: "(де X це номер тесту, починаючи з 1 ), а потім A, якщо переможе Аліса, або B, якщо виграє Боб.