Logging

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

The boundary of the forest is the convex polygon of smallest area that contains every tree, the shape you get by stretching a giant rubber band 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. The squirrels want to know how close their own trees are to being on the boundary.

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

Report every number written on the log.

The first line contains the number of test cases, $T$. $T$ test cases follow. The first line of each test case contains the number of trees, $N$. The next $N$ lines each contain two space separated integers $X_i$ and $Y_i$, the coordinates of one tree. No two trees share the same coordinates.

Limits

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

For each test case, print Case #x: first, where $x$ is the test case number starting at 1. Then print $N$ lines with one integer each. Line $i$ holds the number of trees 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. Cutting one tree puts the fifth tree on the boundary, so its squirrel writes 1.