킹

Alice와 Bob은 게임을 하려고 한다. 게임은 R개의 행과 C개의 열로 이루어져 총 RC개의 칸이 있는 체스판에서 진행된다. 이 칸들 중 일부는 불타 있다.

체스판의 불타지 않은 칸에 킹 하나를 놓고, Alice와 Bob이 번갈아 킹을 움직인다.

한 번의 이동에서 플레이어는 다음 두 조건을 만족하면서 킹과 인접한 8개의 칸 중 어느 한 칸으로 킹을 움직여야 한다.

• 도착할 칸은 불타 있지 않아야 한다.

• 킹이 이전에 도착할 칸에 있었던 적이 없어야 한다.

이동할 수 없는 플레이어가 게임에서 진다. Alice가 먼저 움직인다. 두 플레이어가 모두 최적으로 플레이한다고 가정할 때 누가 이기는지 결정해야 한다.

제한

메모리 제한: 1GB. 1 ≤ N ≤ 100

작은 데이터 세트 (테스트 세트 1 - 공개)

시간 제한: 30초. 1 ≤ R, C ≤ 4

큰 데이터 세트 (테스트 세트 2 - 비공개)

시간 제한: 180초. 1 ≤ R, C ≤ 15

입력의 첫째 줄에는 테스트 케이스의 수 N이 주어진다.

이어서 N개의 테스트 케이스가 주어진다. 각 테스트 케이스의 첫째 줄에는 두 정수 R과 C가 주어진다. 다음 R개 줄에는 각 행의 C개 칸을 나타내는 길이 C의 문자열이 주어진다. 각 문자열에는 문자 '.', '#', 'K'만 포함된다.

• '#'은 해당 칸이 불타 있음을 뜻한다.

• '.'은 해당 칸이 불타지 않았으며 비어 있음을 뜻한다.

• 'K'는 게임을 시작할 때 킹이 해당 칸에 있음을 뜻한다.

각 테스트 케이스에는 'K' 문자가 정확히 하나만 존재한다.

각 테스트 케이스마다 "Case #X: "을 한 줄에 출력하고(여기서 X는 1부터 시작하는 테스트 케이스 번호이다), 그 뒤에 Alice가 이기면 A를, Bob이 이기면 B를 출력한다.