Description

本题的前两段（不包括本段）与“New Elements: Part 2”完全相同。除此之外，这两道题可以独立解决；你无需阅读或解决其中一道即可理解或解决另一道。

Muriel 正在探索两种新元素，并将它们命名为 Codium 和 Jamarium。她尚未能够分离出这两种元素，但她希望通过间接方法研究它们的一些重要性质，比如它们的原子量。由于 Muriel 只研究 Codium 和 Jamarium 的单一同位素，因此它们的原子量都是严格正整数。

Muriel 成功合成了 $\mathbf{N}$ 种不同的分子，每种分子都只包含一种或多种 Codium 原子和一种或多种 Jamarium 原子，不含其他元素。对于每种分子，她都知道其中包含的每种元素的原子数。分子的分子量等于其所含所有原子的原子量之和。

为了进一步确定分子的精确分子量以及两种元素的原子量，Muriel 首先希望将这些分子按分子量严格递增的顺序排序。为了评估这个任务的难度，她想知道在当前信息下，有多少种排序方式是有效的。一个分子的排序被认为是有效的，当且仅当存在 Codium 和 Jamarium 的原子量的取值，使得该排序下分子的分子量严格递增。

举个例子，我们用每个分子中 Codium 和 Jamarium 原子的数量对其进行表示。如果 Muriel 有 3 个分子，分别为 $(1, 1)$、$(2, 1)$ 和 $(1, 2)$，则有两种可能的排序可以使分子量严格递增：$(1, 1)$、$(1, 2)$、$(2, 1)$ 和 $(1, 1)$、$(2, 1)$、$(1, 2)$。第一种排序在 Codium 比 Jamarium 重时成立，第二种排序在 Jamarium 比 Codium 重时成立。剩下的唯一情况是 Codium 和 Jamarium 的原子量相等，此时 $(1, 2)$ 和 $(2, 1)$ 的分子量相等，因此无法得到严格递增的排序。

Input Format

输入的第一行为测试用例数 $\mathbf{T}$。接下来有 $\mathbf{T}$ 组测试数据。每组测试数据的第一行为一个整数 $\mathbf{N}$，表示分子的数量。接下来的 $\mathbf{N}$ 行，每行包含两个整数 $\mathbf{C_i}$ 和 $\mathbf{J_i}$，分别表示第 $i$ 个分子中 Codium 和 Jamarium 的原子数。

Output Format

对于每组测试数据，输出一行，格式为 Case #x: y，其中 $x$ 是测试用例编号（从 1 开始），$y$ 是满足条件的有效排序总数。

3
3
1 1
1 2
2 1
4
1 2
2 4
2 1
4 2
3
1 2
1 3
2 3

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

Hint

样例解释

样例 1 已在题目描述中解释。

在样例 2 中，两种有效的排序分别为 $(1, 2)$、$(2, 1)$、$(2, 4)$、$(4, 2)$ 和 $(2, 1)$、$(1, 2)$、$(4, 2)$、$(2, 4)$。注意，排序 $(1, 2)$、$(2, 1)$、$(2, 4)$、$(4, 2)$、$(2, 4)$ 是无效的，因为如果 $(1, 2)$ 的分子量严格小于 $(2, 1)$，那么 $(2, 4)$（正好是 $(1, 2)$ 的两倍）也必须严格小于 $(4, 2)$（正好是 $(2, 1)$ 的两倍）。

数据范围

• $1 \leqslant \mathbf{T} \leqslant 100$。
• $1 \leqslant \mathbf{C_i} \leqslant 10^9$，对所有 $i$。
• $1 \leqslant \mathbf{J_i} \leqslant 10^9$，对所有 $i$。
• 对于所有 $i \neq j$，$(\mathbf{C_i}, \mathbf{J_i}) \neq (\mathbf{C_j}, \mathbf{J_j})$（所有分子都不同）。

测试点 1（8 分，可见）

• $2 \leqslant \mathbf{N} \leqslant 6$。

测试点 2（14 分，隐藏）

• $2 \leqslant \mathbf{N} \leqslant 300$。

由 ChatGPT 4.1 翻译