Một khu rừng có \(N\) cây, mỗi cây là nơi ở của một chú sóc.

Biên của khu rừng là đa giác lồi có diện tích nhỏ nhất chứa mọi cây, giống như một sợi dây cao su khổng lồ được căng quanh phía ngoài khu rừng.

Nói chính xác, mỗi cây là một điểm trong không gian hai chiều, có tọa độ \((X_i,Y_i)\) riêng biệt, và biên là bao lồi của các điểm đó.

Một số cây nằm trên biên khu rừng, nghĩa là chúng nằm trên một cạnh hoặc một đỉnh của đa giác. Các chú sóc muốn biết cây của mình gần với việc nằm trên biên đến mức nào.

Lần lượt từng chú sóc trèo xuống khỏi cây, quan sát khu rừng và xác định số cây ít nhất cần bị chặt để cây của chính nó nằm trên biên. Sau đó, nó ghi con số ấy lên một khúc gỗ.

Hãy xác định danh sách các số được ghi trên khúc gỗ.

Dữ liệu vào

Dòng đầu tiên chứa số bộ test \(T\). Mỗi bộ test gồm một dòng chứa số nguyên \(N\), là số cây, tiếp theo là \(N\) dòng, mỗi dòng chứa hai số nguyên cách nhau bởi dấu cách \(X_i\) và \(Y_i\), là tọa độ của một cây. Không có hai cây nào có cùng tọa độ.

Dữ liệu ra

Với mỗi bộ test, in một dòng Case #x:, sau đó là \(N\) dòng, mỗi dòng chứa một số nguyên; dòng thứ \(i\) là số cây mà chú sóc sống trên cây \(i\) cần chặt.

Ràng buộc

• \(-10^6 \le X_i,Y_i \le 10^6\).

Phân nhóm

• Nhỏ: \(1 \le T \le 100\); \(1 \le N \le 15\).
• Lớn: \(1 \le T \le 14\); \(1 \le N \le 3000\).

Điểm các phân nhóm

Mỗi Test Set tương ứng với một subtask trên LQDOJ. Bảng dưới đây giữ nguyên điểm chính thức của Google Code Jam và quy đổi tỷ lệ trên tổng điểm của bài.

Ví dụ

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

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

Nguồn

Google Code Jam 2015, Vòng 1A, bài Logging.

Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.