Description

一支足球队将要分排站好拍照。每位球员的位置由两个整数 $x$ 和 $y$ 给出，其中 $y$ 表示排号，$x$ 表示该球员距离本排左边缘的距离。所有球员的 $x$ 值都互不相同。

为了让照片更有趣，你希望相邻的球员穿不同颜色的球衣。为此，你设定了如下规则：

对于每一个球员 $P$：

• 如果 $P$ 这一排中，右侧最近的球员存在，则他们两人的球衣颜色必须不同。
• 如果 $P$ 的上一排中，右侧最近的球员存在，则他们的球衣颜色必须不同。
• 如果 $P$ 的下一排中，右侧最近的球员存在，则他们的球衣颜色必须不同。

更正式地说，若存在球员分别在 $(x_1, y_1)$ 和 $(x_2, y_2)$，且 $x_1 < x_2$，那么当满足以下条件时，这两名球员的球衣颜色必须不同：

• $y_1 - 1 \leq y_2 \leq y_1 + 1$，并且
• 不存在 $x_3$ 使得在 $(x_3, y_2)$ 有球员，且 $x_1 < x_3 < x_2$。

请你求出，满足上述要求所需的最少球衣颜色数。

Input Format

输入的第一行包含一个整数 $T$，表示测试用例数量。每组测试用例的第一行为一个整数 $N$，表示球员数量，接下来 $N$ 行，每行两个整数 $x\ y$，表示一名球员的位置。

Output Format

对于每组测试用例，输出

Case #X: $c$

其中 $X$ 是测试用例编号（从 $1$ 开始），$c$ 是所需的最少颜色数。

3
3
10 10
8 15
12 7
5
1 1
2 1
3 1
4 1
5 1
3
1 1
2 2
3 1

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

Hint

限制条件

• $1 \leqslant T \leqslant 100$
• $1 \leqslant x \leqslant 1000$
• 所有 $x$ 值均互不相同。

小数据集（8 分）

• $1 \leqslant y \leqslant 15$
• $1 \leqslant N \leqslant 100$

大数据集（19 分）

• $1 \leqslant y \leqslant 30$
• $1 \leqslant N \leqslant 1000$

翻译由 ChatGPT-4.1 完成。