벌목 기록 (라지)

어떤 숲에 나무가 $N$그루 있고, 나무마다 다람쥐가 한 마리씩 산다.

숲의 경계는 모든 나무를 품는 가장 작은 볼록 다각형이다. 숲 바깥에 커다란 고무줄을 두르고 팽팽하게 당긴 모양이라고 생각하면 된다.

나무는 각각 평면 위의 한 점이고, 좌표 $(X_i, Y_i)$는 모두 다르다. 경계는 이 점들의 볼록 껍질이다.

어떤 나무는 경계 위에 있다. 다각형의 변이나 꼭짓점에 놓여 있다는 뜻이다. 바꿔 말하면, $i$번 나무를 지나는 직선을 하나 잡아 나머지 나무가 모두 그 직선 위에 있거나 직선의 한쪽에만 있게 만들 수 있으면 $i$번 나무는 경계 위에 있다. 나무가 모두 한 직선 위에 있거나 나무가 한 그루뿐인 경우에도 이 정의를 그대로 쓴다.

다람쥐들은 한 마리씩 차례로 나무에서 내려와 숲을 살펴보고, 자기 나무가 경계 위에 놓이려면 나무를 최소 몇 그루 베어야 하는지 계산한다. 그리고 그 수를 통나무에 적는다.

통나무에 적힌 수를 모두 구하라.

첫 줄에 테스트 케이스의 수 $T$가 주어진다. 각 테스트 케이스의 첫 줄에는 나무의 수 $N$이 주어지고, 이어지는 $N$개의 줄에 나무 하나의 좌표 $X_i$와 $Y_i$가 공백으로 구분되어 주어진다. 좌표가 같은 나무는 없다.

제한

• $1 \le T \le 14$
• $1 \le N \le 3000$
• $-10^6 \le X_i, Y_i \le 10^6$

각 테스트 케이스마다 Case #x:를 한 줄에 출력한다. $x$는 1부터 시작하는 테스트 케이스 번호다. 이어서 $N$개의 줄에 정수를 하나씩 출력한다. $i$번째 줄에는 $i$번 나무에 사는 다람쥐가 베어야 하는 나무의 수를 적는다.

첫 번째 예제의 첫 테스트 케이스에는 정사각형을 이루는 나무 네 그루와 그 안쪽의 나무 한 그루가 있다. 앞의 네 그루는 이미 경계 위에 있으므로 그 다람쥐들은 모두 0을 적는다. 다섯 번째 나무는 한 그루만 베면 경계 위에 놓이므로 그 다람쥐는 1을 적는다.