Logging (Large)

A forest has $N$ trees, and a squirrel lives in each one.

The boundary of the forest is the convex polygon of smallest area that contains every tree, as if a giant rubber band had been stretched around the outside of the forest.

Each tree is a single point in the plane, and the coordinates $(X_i, Y_i)$ are all different. The boundary is the convex hull of those points.

Some trees are on the boundary, which means they lie on an edge or a corner of the polygon. Put another way, tree $i$ is on the boundary when you can draw a line through tree $i$ that leaves every other tree on the line or on one side of it. The same definition applies when all trees are collinear and when there is only one tree.

One at a time, each squirrel climbs down, looks at the forest, and works out the minimum number of trees that would have to be cut down for its own tree to be on the boundary. It then writes that number on a log.

Determine the list of numbers written on the log.

The first line contains the number of test cases, $T$. The first line of each test case contains $N$, the number of trees, followed by $N$ lines with two space separated integers $X_i$ and $Y_i$, the coordinates of one tree. No two trees have the same coordinates.

Limits

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

For each test case, print one line containing Case #x:, where $x$ is the test case number starting from 1. Then print $N$ lines with one integer each. Line $i$ holds the number of trees that the squirrel living in tree $i$ would have to cut down.

In the first test case of the first example, four trees form a square and a fifth tree sits inside it. The first four trees are already on the boundary, so those squirrels each write 0. One tree has to be cut down for the fifth tree to reach the boundary, so the fifth squirrel writes 1.