킹 게임

앨리스와 밥이 체스판 위에서 게임을 한다. 체스판은 $R$개의 행과 $C$개의 열, 모두 $RC$개의 칸으로 이루어진다. 이 중 몇 칸은 불에 타 있다.

타지 않은 칸 하나에 킹을 놓고, 앨리스와 밥이 번갈아 킹을 한 칸씩 움직인다.

한 차례에는 킹을 현재 칸과 인접한 8개의 칸 중 하나로 옮겨야 하고, 다음 두 조건을 지켜야 한다.

• 옮겨 갈 칸은 타지 않은 칸이어야 한다.
• 킹이 그 칸에 한 번도 들어간 적이 없어야 한다. 시작 칸도 이미 들어간 칸으로 센다.

자기 차례에 킹을 움직일 수 없는 사람이 진다. 앨리스가 먼저 움직인다. 두 사람이 모두 최선으로 움직일 때 누가 이기는지 구하라.

첫째 줄에 테스트 케이스의 개수 $N$이 주어진다.

다음으로 $N$개의 테스트 케이스가 이어진다. 각 테스트 케이스의 첫째 줄에는 두 정수 $R$와 $C$가 주어진다. 이어지는 $R$개의 줄에는 각각 길이 $C$의 문자열이 주어지고, 한 줄이 그 행의 $C$개 칸을 나타낸다. 문자열은 ., #, K 세 문자로만 이루어진다.

• #은 타 버린 칸이다.
• .은 타지 않았고 비어 있는 칸이다.
• K는 게임을 시작할 때 킹이 놓인 칸이다. 이 칸은 타지 않은 칸이다.

각 테스트 케이스에 K는 정확히 하나 있다.

각 테스트 케이스마다 한 줄에 Case #X: 를 출력한 다음, 앨리스가 이기면 A, 밥이 이기면 B를 이어서 출력한다. $X$는 1부터 시작하는 테스트 케이스 번호다.

• $1 \le N \le 100$
• $1 \le R, C \le 15$