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