추격 게임

두 플레이어 A와 B가 N x N 정사각형 보드에서 게임을 한다. 두 플레이어는 각각 하나의 시작 칸에서 출발한다. 보드의 각 칸은 흰 칸 또는 검은 칸이며, 검은 칸으로는 지나갈 수 없다. A와 B의 시작 칸은 검은 칸이 아니다.

각 턴에 현재 플레이어는 상하좌우로 인접한 칸 중 하나로 한 번 이동한다. 이때 이동한 칸이 상대방의 현재 위치와 같아지면, 현재 플레이어는 즉시 상하좌우 중 한 방향으로 한 번 더 이동할 수 있다.

A가 먼저 턴을 시작한다. 상대방의 시작 칸에 먼저 도착하는 플레이어가 승리한다. 두 플레이어가 모두 최선의 전략을 사용한다고 할 때, 누가 이기는지 구하라.

첫째 줄에 테스트 케이스의 개수 t (1 <= t <= 10)가 주어진다.

각 테스트 케이스는 먼저 보드의 크기 n (1 <= n <= 300)으로 시작한다. 이어서 n개의 줄에 보드가 주어진다. A와 B는 두 플레이어의 시작 위치를 나타내고, .는 흰 칸, #는 검은 칸을 나타낸다.

각 테스트 케이스마다 승자를 입력 순서대로 출력한다. A가 이기면 A, B가 이기면 B를 출력한다.

첫 번째 공개 테스트 케이스에서는 A가 어느 방향으로 움직여도 B가 따라가면, B의 세 번째 이동에서 A의 현재 위치와 겹칠 수 있다. 그러면 B는 추가 이동을 한 번 얻고 A의 시작 위치에 더 먼저 도착할 수 있다.

두 번째 공개 테스트 케이스에서는 A가 B와 만나지 않는 경로를 선택할 수 있다. 서로 만나지 않으면 먼저 시작한 A가 승리한다.