인접한 연속 번호

두 플레이어 A와 B가 게임을 하고 있다. 이 게임에서는 1부터 N까지 번호가 매겨진 N개의 타일과, 비어 있는 N개의 칸이 하나의 가로줄로 배열된 보드를 사용한다.

플레이어들은 번갈아 차례를 진행하며, 플레이어 A가 먼저 한다. 자기 차례가 되면 플레이어는 사용하지 않은 타일 하나와 빈 칸 하나를 골라 그 칸에 타일을 놓는다. 게임이 끝났을 때 번호가 연속하는 두 타일이 인접한 칸에 있으면 누가 그 타일들을 놓았는지와 관계없이 플레이어 A가 승리한다. 그렇지 않으면 플레이어 B가 승리한다. 예를 들어 최종 보드 1 2 3 4와 4 1 3 2은 플레이어 A가 승리하는 예이고, 최종 보드 3 1 4 2은 플레이어 B가 승리하는 예이다. 연속하는 번호는 어느 순서로 나타나도 된다는 점에 유의하라.

당신은 방금 두 플레이어가 게임하는 것을 지켜봤지만, 그들의 전략을 이해하지 못했다. 그들은 합리적으로 플레이하지 않았을 수도 있다! 당신은 그들의 수를 최적 전략과 비교하기로 한다.

승리 상태란 상대가 무엇을 하든 자기 차례인 플레이어가 최적으로 플레이하면 승리를 보장할 수 있는 게임 상태이다. 실수란 승리 상태에서 둔 수로 인해 다음 차례의 상대가 승리 상태를 갖게 되는 것이다. 게임의 마지막 차례에는 실수할 수 없다는 점에 유의하라. 마지막 차례가 그 플레이어의 승리 상태로 시작했다면, 그 플레이어가 둘 수 있는 유일한 수가 반드시 승리로 이어지기 때문이다.

N개의 수가 주어질 때, 각 플레이어가 저지른 실수의 수를 센다.

제한

테스트 세트별 시간 제한: 40초. 메모리 제한: 1GB. 1 ≤ T ≤ 100. 모든 i에 대해 1 ≤ $M_{i}$ ≤ N. 모든 i ≠ j에 대해 $M_{i}$ ≠ $M_{j}$. 모든 i에 대해 1 ≤ $C_{i}$ ≤ N. 모든 i ≠ j에 대해 $C_{i}$ ≠ $C_{j}$.

테스트 세트 1 (결과 공개)

4 ≤ N ≤ 10.

테스트 세트 2 (결과 비공개)

4 ≤ N ≤ 50.

입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 게임에 사용되는 타일의 수인 정수 N이 담긴 한 줄로 시작한다. 이는 차례의 수이자 보드에 있는 칸의 수도 된다.

그다음 N개의 줄이 더 주어진다. 이 중 1부터 세었을 때 i번째 줄에는 두 정수 $M_{i}$와 $C_{i}$가 주어진다. 이들은 각각 i번째 차례에 고른 타일과 그 타일을 놓은 칸의 인덱스를 나타낸다. 칸의 인덱스는 왼쪽 끝의 1부터 오른쪽 끝의 N까지 센다.

i가 홀수일 때마다 플레이어 A의 차례이고, i가 짝수일 때마다 플레이어 B의 차례임에 유의하라.

각 테스트 케이스마다 Case #x: a b을 포함하는 한 줄을 출력한다. 여기서 x는 1부터 시작하는 테스트 케이스 번호이고, a는 플레이어 A가 저지른 실수의 총개수이며, b는 플레이어 B가 저지른 실수의 총개수이다.

모든 게임은 항상 플레이어 A의 승리 상태로 시작한다는 점에 유의하라. 예를 들어 플레이어 A는 타일 2를 칸 2, 즉 왼쪽에서 두 번째 칸에 놓을 수 있다. 플레이어 B가 자기 차례에 무엇을 하든 타일 1와 3 중 적어도 하나는 사용되지 않은 상태이고, 칸 1과 3 중 적어도 하나는 비어 있다. 그러면 플레이어 A는 그 타일들 중 하나를 그 칸들 중 하나에 놓을 수 있으며, 이렇게 하면 게임의 나머지 과정에서 무슨 일이 일어나든 플레이어 A의 승리가 보장된다.

예제 케이스 #1에서 게임은 다음과 같이 진행된다.

• _ _ _ _ _ _. 위에서 설명했듯이 이는 플레이어 A의 승리 상태이다.

• 차례 1: 플레이어 A가 타일 2를 칸 2에 놓는다.

• _ 2 _ _ _ _. 위에서 설명했듯이 이는 플레이어 B의 승리 상태가 아니다. 플레이어 B는 게임에서 남은 선택을 어떻게 하더라도 승리를 보장할 수 없다.

• 차례 2: 플레이어 B가 타일 3를 칸 5에 놓는다.

• _ 2 _ _ 3 _. 이는 플레이어 A의 승리 상태이다. 예를 들어 타일 1를 칸 3에 놓을 수 있다.

• 차례 3: 플레이어 A가 타일 4를 칸 3에 놓는다.

• _ 2 4 _ 3 _. 이는 플레이어 B의 승리 상태이다. 예를 들어 플레이어 B는 타일 5를 칸 1에 놓을 수 있으며, 그러면 플레이어 A가 무엇을 하든 승리가 보장된다. 따라서 플레이어 A가 직전에 둔 수는 실수였다!

• 차례 4: 플레이어 B가 타일 6를 칸 6에 놓는다.

• _ 2 4 _ 3 6. 플레이어 A가 타일 1를 칸 1에 놓을 수 있으므로 이는 플레이어 A의 승리 상태이다. 따라서 플레이어 B가 직전에 둔 수는 실수였다!

• 차례 5: 플레이어 A가 타일 1를 칸 4에 놓는다.

• _ 2 4 1 3 6. 이는 플레이어 B의 승리 상태이므로 플레이어 A가 직전에 둔 수는 실수였다!

• 차례 6: 플레이어 B가 타일 5를 칸 1에 놓는다.

• 5 2 4 1 3 6. 게임이 끝났고 플레이어 B가 승리했다.

총합하면 플레이어 A는 2번 실수했고 플레이어 B는 1번 실수했다.

예제 케이스 #2에서는 일부 수가 위험해 보일 수 있지만, 어느 플레이어도 이 문제에서 정의한 실수를 저지르지 않았다. 플레이어 A는 승리 상태를 플레이어 B에게 넘겨준 적이 없고, 플레이어 B는 승리 상태였던 적이 없으므로 실수할 기회가 없었다.

예제 케이스 #3에서는 두 번째 수가 인접하면서 번호가 연속하는 타일 한 쌍을 만들기 때문에 두 번째 수를 둔 뒤 게임의 결과가 결정되지만, 각 게임에서 모든 타일을 반드시 놓아야 한다는 점에 유의하라. 또한 두 번째 수로 플레이어 A의 승리가 확정되지만, 당시 플레이어 B는 승리 상태가 아니었으므로 그 수는 플레이어 B의 실수가 아니다.