벌목

어떤 숲은 N그루의 나무로 이루어져 있으며, 각 나무에는 다람쥐 한 마리가 살고 있다.

숲의 경계는 숲 바깥쪽에 거대한 고무줄을 둘러 팽팽하게 당긴 것처럼, 모든 나무를 포함하는 가장 작은 넓이의 볼록다각형이다.

형식적으로, 각 나무는 고유한 좌표 ($X_{i}$, $Y_{i}$)를 갖는 이차원 공간의 한 점이며, 경계는 이 점들의 볼록 껍질이다.

일부 나무는 숲의 경계에 있으며, 이는 그 나무가 다각형의 변이나 꼭짓점 위에 있다는 뜻이다. 다람쥐들은 자신의 나무가 숲의 경계에 얼마나 가까이 있는지 궁금해한다.

한 번에 한 마리씩, 각 다람쥐는 자신의 나무에서 내려와 숲을 살펴보고, 자신의 나무가 경계에 놓이게 하려면 잘라야 하는 나무의 최소 개수를 구한다. 그런 다음 그 수를 통나무에 적는다.

통나무에 적힌 수의 목록을 구하라.

제한

메모리 제한: 1 GB. -$10^{6}$ ≤ $X_{i}$, $Y_{i}$ ≤ $10^{6}$.

소규모 데이터 세트

시간 제한: 240초. 1 ≤ T ≤ 100. 1 ≤ N ≤ 15.

대규모 데이터 세트

시간 제한: 480초. 1 ≤ T ≤ 14. 1 ≤ N ≤ 3000.

입력의 첫 번째 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 나무의 수를 나타내는 정수 N이 있는 한 줄과, 그 뒤에 각 나무의 좌표인 공백으로 구분된 두 정수 $X_{i}$와 $Y_{i}$가 있는 N개의 줄로 구성된다. 어떤 두 나무도 같은 좌표를 갖지 않는다.

각 테스트 케이스마다 "Case #x:"이 포함된 한 줄을 출력한 뒤, 각각 하나의 정수가 있는 N개의 줄을 출력한다. 이때 i번째 줄에는 i번째 나무에 사는 다람쥐가 잘라야 하는 나무의 수를 출력한다.

첫 번째 예제 케이스에는 정사각형을 이루는 나무 네 그루와 정사각형 내부의 다섯 번째 나무가 있다. 처음 네 그루의 나무는 이미 경계에 있으므로, 그 나무들의 다람쥐는 각각 0을 적는다. 다섯 번째 나무가 경계에 놓이려면 나무 한 그루를 잘라야 하므로, 다섯 번째 다람쥐는 1을 적는다.