극한 틱택토

문제

틱택토(Tic-Tac-Toe, 영어로는 Noughts and Crosses)는 아이들이 종이와 연필로 즐기는 간단한 놀이입니다. 두 사람이 번갈아 가며 $3 \times 3$ 격자의 칸에 자신의 기호(O 또는 X)를 그립니다. 가로, 세로, 대각선 중 어느 방향으로든 자신의 기호 3개를 한 줄로 먼저 완성하는 사람이 이깁니다. 아무도 한 줄을 완성하지 못한 채 격자가 가득 차면 비깁니다. 아래는 X가 방금 이긴 판입니다.

이 놀이는 다소 단순합니다. 흥미로운 확장은 이를 3차원으로 만드는 것입니다. 즉 $3 \times 3$ 격자를 3층으로 쌓습니다. 진짜 3차원 판은 별도의 도구가 필요하지만(상용 플라스틱 세트도 있습니다), $3 \times 3$ 격자 3개를 그려 놓고 서로 위에 쌓여 있다고 상상하면 종이 위에서도 즐길 수 있습니다. 아래에서 X가 또 이겼습니다.

그렇다면 4차원, 5차원, 6차원에서 두면 어떨까요? 이것이 바로 극한 틱택토(Extreme Tic-Tac-Toe, ETTT)의 기본 아이디어입니다. ETTT의 점수 계산 방식은 보통의 틱택토와 다릅니다. 한 사람이 한 줄을 완성하는 순간 멈추는 대신, ETTT에서는 격자가 가득 찰 때까지(또는 두 사람이 합의하여 멈출 때까지) 계속 둡니다. 자신의 기호로 이루어진 줄(line)을 더 많이 만든 사람이 승자입니다. ETTT 규칙에 따르면 아래 3차원 판에서 X는 4점, O는 1점을 얻습니다.

여러분의 과제는 N차원 ETTT 판을 읽어 각 기호의 점수를 계산하는 프로그램을 작성하는 것입니다.

여기서 한 줄(line)이란 격자에서 일직선으로 놓인 서로 다른 세 칸의 모임을 뜻합니다. 각 차원마다 그 좌표는 (1) 어떤 값으로 고정되어 있거나, (2) $1, 2, 3$으로 증가하거나, (3) $3, 2, 1$로 감소하며, 적어도 한 차원에서는 좌표가 변해야 합니다. 한 줄을 이루는 세 칸이 모두 같은 기호(모두 X 또는 모두 O)이면 그 기호의 점수가 1 올라갑니다. 빈 칸(~)이 하나라도 포함된 줄은 어느 쪽의 점수도 되지 않습니다.

입력

입력은 여러 개의 ETTT 판 구성으로 이루어집니다. 각 판 구성은 이 게임의 차원 $N$을 담은 한 줄로 시작합니다 ($1 \le N \le 10$). $N$이 $0$이면 입력이 끝났다는 뜻입니다.

그 다음에는 각 칸의 값을 나타내는 X, O, ~ 문자들이 이어집니다(~는 빈 칸을 뜻합니다). 각 줄에는 최소 $1$개, 최대 $40$개의 기호가 들어 있습니다. 데이터가 입력되는 순서는 판이 $N$차원 배열에 담겨 있다고 상상하면 됩니다. 예를 들어 $N = 5$이면 각 칸을 cell[a][b][c][d][e]로 접근할 수 있습니다. 다음 의사코드는 (줄바꿈은 무시하고) 데이터를 올바른 순서로 읽습니다.

for a = 1 to 3
   for b = 1 to 3
      for c = 1 to 3
         for d = 1 to 3
            for e = 1 to 3
               read cell[a][b][c][d][e]

즉 각 판에는 정확히 $3^N$개의 칸이 있으며, 마지막 차원의 좌표가 가장 빠르게 변합니다. 줄바꿈은 무시하고 문자들을 순서대로 읽으면 됩니다.

출력

각 판 구성마다 X의 점수와 O의 점수를 한 줄에 다음 형식으로 출력합니다.

X scores A and O scores B

여기서 $A$는 X 기호로만 이루어진 줄의 개수, $B$는 O 기호로만 이루어진 줄의 개수입니다.