熊猫先生喜欢创作和解决数学谜题。有一天，熊猫先生在玩多米诺骨牌时想到了一个谜题。

在一个由无限行和无限列组成的网格中，除了给定的 $N$ 个黑色单元格以外，所有单元格均为白色。熊猫先生想知道网格中有多少个多米诺骨牌。

多米诺骨牌是一个满足以下要求的矩形：

• 该多米诺骨牌由网格中连续的行和列组成。
• 该多米诺骨牌至少包含 1 行和 1 列。
• 多米诺骨牌边缘上的单元格均为黑色。这意味着最顶行、最底行、最左列和最右列仅由黑色单元格组成。
• 多米诺骨牌的纵横比为 $2:1$ 或 $1:2$。这意味着，如果多米诺骨牌有 $k$ 列，则它应该有 $2k$ 行；或者如果它有 $k$ 行，则它应该有 $2k$ 列（在这种情况下 $k$ 是偶数）。

例如，在下图中，左侧的 $3 \times 3$ 网格包含 6 个多米诺骨牌（4 个 $1 \times 2$ 的多米诺骨牌和 2 个 $2 \times 1$ 的多米诺骨牌），右侧的 $3 \times 6$ 网格包含 15 个多米诺骨牌（10 个 $1 \times 2$ 的多米诺骨牌，4 个 $2 \times 1$ 的多米诺骨牌和一个 $3 \times 6$ 的多米诺骨牌）。

由于网格非常巨大，熊猫先生太懒了，不想去数多米诺骨牌的数量。你能帮熊猫先生找出网格中有多少个多米诺骨牌吗？

输入格式

输入的第一行包含测试用例的数量 $T$。接下来是 $T$ 个测试用例。 每个测试用例的第一行包含一个整数 $N$，表示网格中黑色单元格的数量。 接下来 $N$ 行，每行包含两个整数 $R_i$ 和 $C_i$，表示黑色单元格所在的行和列。

$1 \le T \le 100$ $1 \le N \le 1,000,000$ $1 \le R_i, C_i \le 1,000,000,000$ 所有测试用例的 $N$ 之和不超过 $5,000,000$ 对于每个测试用例，没有两个黑色单元格位于同一位置。

输出格式

对于每个测试用例，输出一行 “Case #x: y”，其中 $x$ 是测试用例编号（从 1 开始），$y$ 是熊猫先生想要知道的第 $i$ 个数据集中的多米诺骨牌数量。

样例

样例输入 1

2
7
1 1
1 2
1 3
2 2
3 1
3 2
3 3
14
1 1
1 2
1 3
1 4
1 5
1 6
2 1
2 6
3 1
3 2
3 3
3 4
3 5
3 6

样例输出 1

Case #1: 6
Case #2: 15