Time Limit: 1000 MS Memory Limit: 65536 K

## Description

Farmer John's farm is a convex polygon combined of n fences. To guarantee that
the animals in the farm, such as cow, will not leave his farm, John employs n
acmers to the mid-point of each fence to watch the animals. When John is back to
his farm, he wants to know whether the acmers are lazy, so he observes how the
acmers work before he comes into the farm. John can choose only one point to
observe, and a fence blocks everything behind it. So he wants to choose one point
such that when all the acmers are on their duty, the number of amcers he can see
is as many as possible. When all the acmers are on their duty, what is maximum
number of acmers he can see? We assume they are all in a plane, and the sight of
John is good enough and we can treat each acmer as a point and treat each fence
as a segment.
## Input

The first line of the input is an integer T which stands for the number of test case.
Then T test cases follow.
The first line of each test case is an integer n, then n lines follow.
Each of the following lines contain two integers seperated by a space which are
the x-coordinate and y-coordinate of a vertex of the convex polygon.
The vertice are given in anticlockwise order.
constraints:
n is in the range of [3, 1000].
x, y is in the range of [-10000, 10000].
## Output

For each test case, output the answer in a single line.
## Sample Input

1
3
0 0
1 0
0 1
## Sample Output

2
## Hint

To see a acmer is to say we can join John and the acmer by a segment and the intersection
between the segment and the polygon is empty.
## Author

baihacker