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