틱택토 이기기

남규는 재우와 틱택토를 두다가 한 수만 더 놓으면 이기는 상황까지 왔다. 남규가 이기기 직전의 게임판이 주어지면, 어디에 말을 놓아야 이기는지 찾아보자.

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

각 테스트 케이스는 네 줄로 이루어진다. 앞의 세 줄은 현재 게임판의 상태이고, 네 번째 줄에는 남규의 말이 x인지 o인지 주어진다. 게임판의 각 칸은 x, o, 빈칸을 뜻하는 - 중 하나다. 남규가 다음 한 수로 반드시 이기는 상태만 입력으로 주어진다.

각 테스트 케이스마다 Case k:를 한 줄에 출력하고, 이어서 남규가 이기는 수를 놓은 뒤의 게임판을 세 줄에 걸쳐 출력한다. k는 1부터 시작하는 테스트 케이스 번호다.

이기는 칸이 여러 개라면 행 번호가 가장 작은 칸에 말을 놓고, 그런 칸이 여럿이면 그중 열 번호가 가장 작은 칸에 놓는다. 행은 위에서부터, 열은 왼쪽에서부터 센다.