1191번 - 게임

드록바와 셰브첸코가 첼시에서 같이 훈련하던 옛날 옛적 어느날 두 선수는 훈련에 지쳐 다음과 같은 게임을 하며 쉬기로 한다.

편의상 두 플레이어를 A, B라고 부를 때, 두 플레이어는 N*N짜리 정사각형 보드의 한 점에서 시작하게 된다.

그래서 A, B는 각각 시작점을 가지게 되고 보드에는 흰 칸과 검은 칸이 있는데 검은 칸은 지나가지 못하는 칸이다.(물론 A, B의 시작점과 검은 칸이 겹치는 경우는 없다.)

플레이어들은 각 턴마다 상, 하, 좌, 우로 한 번씩 움직일 수 있다. 그리고 만약 플레이어가 움직여서 상대방의 현 위치와 겹치게 되면 그 플레이어는 상, 하, 좌, 우중 한 방향으로 한 번 더 움직일 수 있는 기회를 받는다.

A플레이어가 먼저 턴을 시작한다고 할 때 상대방의 시작점으로 먼저 도착하는 사람이 경기의 승자가 된다. 양 선수는 최선의 전략을 사용한다고 가정할 때 누가 승자가 될지 알아 보아라.

첫째 줄에는 테스트 데이터의 개수 t (1<=t<=10)가 들어온다. 그리고 다음 t개의 세트에는 우선 맵의 크기 n(1<=n<=300)이 주어지고 다음에는 N*N짜리 지도가 주어지는데 A의 위치와 B의 위치가 표시되어있고 흰자리는 ‘.’, 검은 자리는 ‘#’으로 표시되어있다.

누가 승리할지 테스트 케이스 순서대로 출력하여라.

첫 번째 테스트 케이스의 경우인데 A가 어떤 방향으로 움직이던 B가 따라가게 된다면 A가 3칸을 움직이고 B가 3칸째 움직이게 될 때 A의 위치와 겹칠 수 있고 그때 B가 한 번의 추가 움직임을 허용 받아 더 먼저 상대의 시작장소로 갈 수 있다. 이는 두 번째 테스트 케이스의 경우인데 이 경우 B가 어떻게 가던 A가 피해간다면 만나지 않을 수 있고 서로 만나지 않는다면 먼저 시작한 A가 승리할 수 있다.