题目描述

两名玩家 A 和 B 正在玩一个游戏。游戏使用编号为 $1$ 到 $\mathbf{N}$ 的 $\mathbf{N}$ 个方块，以及一个由 $\mathbf{N}$ 个空格组成的水平排列的游戏板。

玩家轮流行动，玩家 A 先手。每回合，玩家选择一个未被使用的方块和一个空格，并将该方块放入空格中。游戏结束时，如果存在两个相邻的格子中的方块编号是连续的（无论顺序如何，例如 $1$ 和 $2$ 或 $2$ 和 $1$），则玩家 A 获胜；否则玩家 B 获胜。例如，最终游戏板为 $1\ 2\ 3\ 4$ 或 $4\ 1\ 3\ 2$ 时玩家 A 获胜，而 $3\ 1\ 4\ 2$ 时玩家 B 获胜。

你刚刚观看了一局游戏，但无法理解他们的策略（他们可能没有采用最优策略）。现在，你需要将他们的操作与最优策略进行对比。

必胜状态 是指当前回合的玩家在采取最优策略后，无论对手如何应对，都能确保自己最终获胜的游戏状态。失误 是指玩家在处于必胜状态时，做出了一个导致对手在下一回合进入必胜状态的操作（注意：游戏的最后一回合不可能出现失误，因为如果最后一回合开始时玩家处于必胜状态，那么他的唯一操作必然直接获胜）。

给定 $\mathbf{N}$ 个操作，计算每名玩家的失误次数。

输入格式

输入第一行给出测试用例数量 $\mathbf{T}$。随后是 $\mathbf{T}$ 个测试用例。每个测试用例的第一行包含一个整数 $\mathbf{N}$，表示游戏中的方块数量（也是回合数和游戏板的格子数）。

接下来的 $\mathbf{N}$ 行，第 $i$ 行（从 $1$ 开始计数）包含两个整数 $\mathbf{M_i}$ 和 $\mathbf{C_i}$，分别表示第 $i$ 回合选择的方块编号和放置的格子索引（$1$ 表示最左端，$\mathbf{N}$ 表示最右端）。

注意：当 $i$ 为奇数时是玩家 A 的回合，偶数时是玩家 B 的回合。

输出格式

对于每个测试用例，输出一行 Case #x: a b，其中 $x$ 为测试用例编号（从 $1$ 开始），$a$ 是玩家 A 的失误总数，$b$ 是玩家 B 的失误总数。

输入输出样例 #1

输入 #1

3
6
2 2
3 5
4 3
6 6
1 4
5 1
4
4 1
1 3
3 4
2 2
4
3 1
2 2
4 3
1 4

输出 #1

Case #1: 2 1
Case #2: 0 0
Case #3: 0 0

说明/提示

样例解释

任何游戏的初始状态都是玩家 A 的必胜状态。例如，玩家 A 可以将方块 $2$ 放在格子 $2$（从左数第二个格子）。无论玩家 B 如何应对，至少方块 $1$ 或 $3$ 未被使用，且格子 $1$ 或 $3$ 为空。之后，玩家 A 可以将其中一个方块放入其中一个格子，从而确保自己最终获胜。

在样例 #1 中，游戏过程如下：

• _ _ _ _ _ _（初始状态，玩家 A 必胜）。
• 回合 1：玩家 A 将方块 $2$ 放入格子 $2$。
• _ 2 _ _ _ _（玩家 B 无法确保必胜）。
• 回合 2：玩家 B 将方块 $3$ 放入格子 $5$。
• _ 2 _ _ 3 _（玩家 A 仍可必胜，例如将方块 $1$ 放入格子 $3$）。
• 回合 3：玩家 A 将方块 $4$ 放入格子 $3$。
• _ 2 4 _ 3 _（此时玩家 B 进入必胜状态，例如下一步可将方块 $5$ 放入格子 $1$，确保最终获胜。因此玩家 A 的这一步是失误！）。
• 回合 4：玩家 B 将方块 $6$ 放入格子 $6$。
• _ 2 4 _ 3 6（玩家 A 可必胜，例如将方块 $1$ 放入格子 $1$。因此玩家 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 并不处于必胜状态。

数据范围

• $1 \leq T \leq 100$。
• 对所有 $i$，$1 \leq M_i \leq N$。
• 对所有 $i \neq j$，$M_i \neq M_j$。
• 对所有 $i$，$1 \leq C_i \leq N$。
• 对所有 $i \neq j$，$C_i \neq C_j$。

测试集 1（10 分，可见判定）

• $4 \leq N \leq 10$。

测试集 2（32 分，隐藏判定）

• $4 \leq N \leq 50$。