你需要雇佣一些人来粉刷围栏。围栏由 10000 个连续的部分组成，编号从 1 到 10000。

你收到了一些油漆工的报价，帮助粉刷围栏。每位油漆工都提议用特定的颜色粉刷围栏的一个连续子集。你需要接受一组报价，使得：

• 围栏的每一部分都被粉刷。
• 粉刷围栏最多使用 3 种颜色。

如果满足这两个要求是可能的，请找出你必须接受的最少报价数量。

输入格式

• 第一行包含一个整数 $T$，表示输入文件中的测试用例数量。

对于每个测试用例：

• 第一行包含一个整数 $N$，表示报价的数量。
• $N$ 行，每行对应一个报价，格式为 "$C$ $A$ $B$"，其中 $C$ 是颜色（由最多 10 个大写字母组成的字符串），$A$ 是要粉刷的第一部分的编号，$B$ 是要粉刷的最后一部分的编号。$1 \le A \le B \le 10000$。

输出格式

• $T$ 行，每行对应输入文件中的一个测试用例，格式为 "Case #$X$: $Y$"，其中 $X$ 是用例编号，$Y$ 是需要接受的报价数量。如果不存在可接受的报价组合，则输出 "Case #$X$: IMPOSSIBLE"。

数据范围

$1 \le T \le 50$

小数据集（测试集 1 - 可见；7 分）

$1 \le N \le 10$

大数据集（测试集 2 - 隐藏；13 分）

$1 \le N \le 300$

样例

样例输入 1

5
2
BLUE 1 5000
RED 5001 10000
3
BLUE 1 6000
RED 2000 8000
WHITE 7000 10000
4
BLUE 1 3000
RED 2000 5000
ORANGE 4000 8000
GREEN 7000 10000
2
BLUE 1 4000
RED 4002 10000
3
BLUE 1 6000
RED 4000 10000
ORANGE 3000 8000

样例输出 1

Case #1: 2
Case #2: 3
Case #3: IMPOSSIBLE
Case #4: IMPOSSIBLE
Case #5: 2

说明

在第一个测试用例中，接受两个报价正好可以粉刷整个围栏，每种颜色粉刷 5000 个部分，且没有重叠。

在第二个用例中，油漆工的粉刷区域会有重叠，这是可以接受的。

在第三个用例中，接受全部四个报价可以覆盖整个围栏，但会使用 4 种不同的颜色，因此不可接受。

在第四个用例中，第 4001 部分无法被粉刷。

在第五个用例中，我们可以只接受第一个和第二个报价，从而成功粉刷围栏。