벌목 기록

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

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

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

어떤 나무는 경계 위에 있다. 다각형의 변이나 꼭짓점에 놓였다는 뜻이다. 다람쥐들은 자기 나무가 경계에 얼마나 가까운지 궁금하다.

다람쥐는 한 마리씩 나무에서 내려와 숲을 둘러본 뒤, 자기 나무가 경계 위에 놓이려면 최소 몇 그루를 베어야 하는지 알아낸다. 그리고 그 수를 통나무에 적는다.

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

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

제한

• $1 \le T \le 100$
• $1 \le N \le 15$
• $-10^6 \le X_i, Y_i \le 10^6$

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

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