E. I am not done yet
time limit per test
1 second
memory limit per test
256 megabytes
input
bedone.in
output
standard output

"I'm not done yet. I'm not done yet. I'm not done yet." said Omda.

We want Omda to be done with Battle rap.

Let's define the map as a 2D plane with $$$N$$$ integer points on it. These points are the positions of rappers.

For Omda to be done with Battle Rap he needs to choose one point and then defeat some number of rappers and remove their points from the map.

Omda becomes done with Battle rap when his point becomes a part of the plane's Convex Hull's perimeter.

You want Omda to be done. So you decided to calculate for each point the minimum number of rappers he needs to defeat, such that this point becomes a part of the plane's Convex Hull's perimeter.

A convex hull is a shape of the minimum area that contains all points on the plane.

Input

The first line of the input contains an integer $$$T$$$ – the number of test cases.

The first line of each test case contains one integer $$$N$$$$$$(3 \leq N \leq 10^3)$$$ – The number of points.

The follow $$$N$$$ lines, every line contains two integers $$$X$$$ and $$$Y$$$ $$$(-10^6 \leq X, Y \leq 10^6)$$$ – the points. No three points lie on one straight line.

It is guaranteed that the sum of $$$N$$$ over all test cases does not exceed $$$10^3$$$.

Output

For each test case print $$$N$$$ lines, Every line contains one integer the minimum number of rappers he needs to defeat, such that this point becomes a part of the plane's Convex Hull's perimeter.

Example
Input
1
5
0 0
100 0
0 100
100 100
49 50
Output
0
0
0
0
1