인접한 연속 숫자

두 플레이어 A와 B가 게임을 한다. 게임에는 1번부터 N번까지 번호가 붙은 타일 N개와, 가로로 한 줄로 늘어선 빈 칸 N개로 이루어진 보드가 쓰인다.

플레이어는 번갈아 두며, A가 먼저 둔다. 한 번의 차례에 플레이어는 아직 쓰지 않은 타일 하나를 고르고, 빈 칸 하나를 골라 그 칸에 타일을 놓는다. 게임이 끝났을 때 인접한 두 칸에 연속된 번호의 타일이 두 개 있으면 A가 이긴다. 누가 놓았는지는 상관없다. 그렇지 않으면 B가 이긴다. 예를 들어 최종 보드가 1 2 3 4나 4 1 3 2이면 A의 승리이고, 3 1 4 2이면 B의 승리이다. 연속된 번호는 어느 순서로 나란히 있어도 된다.

방금 두 플레이어가 게임하는 것을 지켜봤지만 전략을 이해할 수 없었다. 합리적으로 두지 않았을 수도 있다. 각 수를 최적 전략과 비교해 보려고 한다.

필승 상태는 차례인 플레이어가 최적으로 두면 상대가 무엇을 하든 이길 수 있는 게임 상태이다. 실수는 필승 상태에서 둔 수 가운데, 그 결과 상대의 다음 차례가 필승 상태가 되는 수이다. (게임의 마지막 차례에는 실수가 나올 수 없다. 마지막 차례가 그 플레이어의 필승 상태에서 시작했다면, 그 플레이어의 유일한 수가 승리로 이어진 것이기 때문이다.)

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

첫 줄에 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 나온다. 각 케이스는 게임에서 쓰이는 타일의 수이자 차례의 수, 보드 칸의 수인 정수 N이 적힌 한 줄로 시작한다.

그 뒤로 N개의 줄이 이어진다. i번째 줄(1부터 셈)에는 정수 Mi와 Ci가 주어진다. 각각 i번째 차례에 고른 타일의 번호와, 그 타일을 놓은 칸의 번호(왼쪽 끝을 1, 오른쪽 끝을 N으로 셈)를 나타낸다.

i가 홀수이면 A의 차례이고, 짝수이면 B의 차례이다.

각 테스트 케이스마다 Case #x: a b 형식으로 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호(1부터 시작), a는 A가 저지른 실수의 총 횟수, b는 B가 저지른 실수의 총 횟수이다.

• 1 ≤ T ≤ 100.
• 모든 i에 대해 1 ≤ Mi ≤ N.
• i ≠ j이면 Mi ≠ Mj.
• 모든 i에 대해 1 ≤ Ci ≤ N.
• i ≠ j이면 Ci ≠ Cj.

게임은 언제나 A의 필승 상태에서 시작한다. 예를 들어 A는 2번 타일을 두 번째 칸에 둘 수 있다. B가 어떤 수를 두더라도 1번과 3번 타일 중 적어도 하나는 아직 쓰지 않았고, 1번과 3번 칸 중 적어도 하나는 비어 있다. 그러면 A가 그 타일과 칸 중 하나를 골라 두면, 나머지 진행과 상관없이 A의 승리가 확정된다.