Given a collection of points in the plane, find the convex polygon with smallest area such that each point is contained within (or on the boundary of) the polygon.

Observe that the vertices of such a polygon will be points from the given collection.

Input

One integer in the first line, stating the number of test cases, followed by a blank line. There will be not more than 15 tests.

For each test case, the first line is an integer n (3 <= n <= 50000) stating the number of points. Then n lines follow, each presenting the coordinate of a point, with two integers x, y (-10000 <= x, y <= 10000). There are no two points which have the same pair of coordinates and no 3 points lie on one straight line.

The test cases will be separated by a single blank line.

Output

For each test case, write one integer - the number of vertices of the convex polygon you've found.

Example

Input:
1

4
0 0
1 0
1 1
0 1


Output:
4