两位玩家 A 和 B 正在进行一场游戏。游戏使用 $N$ 个编号为 $1$ 到 $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$ 开始计数）包含两个整数 $M_i$ 和 $C_i$。它们分别代表在第 $i$ 回合选择的棋子编号，以及该棋子放置的单元格索引（从左端的 $1$ 到右端的 $N$）。

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

输出格式

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

数据范围

$1 \le T \le 100$ $1 \le M_i \le N$，对于所有 $i$ $M_i \neq M_j$，对于所有 $i \neq j$ $1 \le C_i \le N$，对于所有 $i$ $C_i \neq C_j$，对于所有 $i \neq j$

子任务 1

$4 \le N \le 10$

子任务 2

$4 \le N \le 50$

样例

样例输入 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 可以在其中一个单元格中放置其中一个棋子，这保证了玩家 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 的获胜状态；例如，他们可以将棋子 $5$ 放在单元格 $1$，然后无论玩家 A 做什么，他们都保证获胜。所以玩家 A 的最后一次移动是一个失误！
• 第 4 回合：玩家 B 将棋子 $6$ 放在单元格 $6$。
• _ 2 4 _ 3 6。这是一个玩家 A 的获胜状态，因为玩家 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 当时并不处于获胜状态。