Kral#3458
Alisa və Bob bir oyun oynayırlar. Oyun sıra və sütundan ibarət lövhədə keçirilir, yəni ümumilikdə R \times C hüceyrə var. Bu hüceyrələrin bəziləri yanmış ola bilər.
Şah bir yanmamış hüceyrədə yerləşdirilib və Alisa ilə Bob növbə ilə şahı hərəkət etdirirlər.
Hər gedişdə oyunçu şahı onun qonşu hüceyrəsindən birinə köçürməlidir, lakin aşağıdakı iki şərtə əməl etməlidir:
Məqsəd hüceyrəsi yanmış olmamalıdır.
Şah heç vaxt əvvəllər olduğu bir hüceyrəyə köçürülməməlidir.
Əgər oyunçu gediş edə bilmirsə, o, məğlub olur. İlk gedişi Alisa edir və siz hər iki oyunçunun optimal oynadığını qəbul edərək, kimin qalib gələcəyini müəyyən etməlisiniz.
Girişin ilk sətrində test nümunələrinin sayı (1 \leq N \leq 100) verilir.
Sonra test nümunələri gəlir. Hər bir test halında ilk sətir iki tam ədəd, və (1 \leq R, C \leq 15) ibarət olacaq. Növbəti sətir hər bir sıranın hüceyrəsini təyin edən uzunluğu olan sətirlərdən ibarət olacaq. Hər bir sətir yalnız ".", "#" və "K" simvollarını ehtiva edəcək:
"#" yanmış hüceyrəni göstərir;
"." hüceyrənin yanmadığını və tutulmadığını göstərir;
"K" oyunun əvvəlində şahın yerləşdiyi hüceyrəni göstərir.
Hər bir testdə yalnız bir hüceyrənin "K" ehtiva edəcəyi təmin edilir.
Hər bir test üçün "Case # : " (burada testin nömrəsidir, -dən başlayaraq) və sonra , əgər Alisa qalib gəlirsə, və ya , əgər Bob qalib gəlirsə, olan bir sətir çıxarın.
Nümunə 1