题目描述

给定一个二维平面上的 $n$ 个互不相同的点构成的集合 $P$。你需要找到一个最大的三角形集合，满足以下条件：

1. 集合中的每个三角形的顶点均来自 $P$，且每个点最多出现在集合中的一个三角形里。
2. 集合中的每个三角形的面积必须为正，即其三个顶点不共线。
3. 任意两个三角形的边，它们的交点要么为空，要么是其中一条边的端点。
4. 任意两个三角形的内部区域的交集要么为空，要么等于其中一个三角形，即一个三角形完全包含另一个三角形。

例如，下图所示的三角形集合满足上述所有条件。

满足条件的三角形集合示例

相反，下图中每一对黄色和红色的三角形均不满足条件。

不满足条件的三角形集合示例

输入格式

第一行输入测试用例的数量 $T$。接下来是 $T$ 个测试用例。

每个测试用例的第一行是一个整数 $n$。随后 $n$ 行，每行包含两个整数 $x_i$ 和 $y_i$，表示第 $i$ 个点的坐标。

输出格式

对于每个测试用例，输出一行 Case #x: y，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是满足条件的最大三角形集合的大小。

然后，输出 $y$ 行，每行包含三个整数 $p_i,q_i,r_i$，表示你构造的第 $i$ 个三角形的顶点是输入中的第 $p_i,q_i,r_i$ 个点（点的编号从 $1$ 开始）。

样例 1

样例 1 输入

3
9
8 2
10 2
2 0
0 5
2 3
10 4
10 0
8 3
2 4
7
0 0
0 3
3 0
0 1
1 0
1 1
2 2
3
0 0
0 1
0 2

样例 1 输出

Case #1: 3
3 4 5
1 7 9
6 2 8
Case #2: 2
2 3 1
6 5 4
Case #3: 0

样例 1 解释

样例 #1 的示意图如下。注意，存在其他有效的构造方式可以达到最大三角形数量。

样例 #2 的示意图如下。同样，存在其他有效的构造方式形成 $2$ 个三角形。

在样例 #3 中，给定的三个点共线，因此无法构成有效的三角形。

注意，输出的三角形顶点顺序可以任意，只要构成有效三角形即可。

数据范围与提示

对于所有数据，保证 $1 \le T \le 100$，$3 \le n \le 3000$，$-10^9 \le x_i,y_i \le 10^9$。对于 $i \ne j$，$(x_i,y_i) \ne (x_j,y_j)$。