一片森林中有 $N$ 棵树，每棵树上都住着一只松鼠。

森林的边界是包含所有树的面积最小的凸多边形，就像在森林外围拉了一根巨大的橡皮筋一样。

形式化地说，每棵树都是二维空间中坐标为 $(X_i, Y_i)$ 的一个点，且坐标互不相同。森林的边界即这些点的凸包。

有些树位于森林的边界上，这意味着它们位于多边形的边或顶点上。松鼠们想知道它们的树距离“位于森林边界上”还有多远。

每只松鼠依次从树上爬下来，观察森林，并确定为了让自己的树位于边界上，最少需要砍掉多少棵树。然后，它将这个数字写在木头上。

请确定写在木头上的数字列表。

输入格式

输入的第一行包含测试用例的数量 $T$。接下来是 $T$ 个测试用例；每个测试用例的第一行是一个整数 $N$，表示树的数量，随后有 $N$ 行，每行包含两个空格分隔的整数 $X_i$ 和 $Y_i$，表示每棵树的坐标。没有两棵树的坐标相同。

输出格式

对于每个测试用例，输出一行 "Case #x:"，后跟 $N$ 行，每行一个整数，其中第 $i$ 行包含住在第 $i$ 棵树上的松鼠需要砍掉的树的数量。

数据范围

内存限制：1 GB。

$-10^6 \le X_i, Y_i \le 10^6$。

小数据集（18 分）

时间限制：10 秒。

$1 \le T \le 100$。

$1 \le N \le 15$。

大数据集（34 分）

时间限制：20 秒。

$1 \le T \le 14$。

$1 \le N \le 3000$。

样例

输入 1

2
5
0 0
10 0
10 10
0 10
5 5
9
0 0
5 0
10 0
0 5
5 5
10 5
0 10
5 10
10 10

输出 1

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

说明

在第一个样例中，有四棵树构成一个正方形，第五棵树在正方形内部。由于前四棵树已经在边界上，这些树上的松鼠都写下 0。由于第五棵树需要砍掉一棵树才能位于边界上，第五只松鼠写下 1。