K. Aeonglass
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

In the Euclidean plane, you are given a polygon $$$P=P_0P_1\cdots P_{n-1}$$$ whose vertices are listed in counterclockwise order.

An angle $$$\alpha$$$ ($$$0 \le \alpha \lt \pi$$$) is a stable direction if and only if there exists a $$$c \in R$$$ such that, for every point $$$X$$$ in polygon $$$P$$$ (including its boundary), the perpendicular segment from $$$X$$$ to the line $$$$$$ \cos \alpha\,x + \sin \alpha\,y + c = 0 $$$$$$ lies entirely in $$$P$$$ (including its boundary). Here $$$\alpha$$$ is a direction of the line's normal vector.

Find the number of stable directions. This number can be shown to be finite.

Input

The first line contains an integer $$$T$$$ ($$$1 \le T \le 100$$$), the number of test cases.

The first line of each test case contains an integer $$$n$$$ ($$$3 \le n \le 10^5$$$), the number of polygon vertices.

Each of the next $$$n$$$ lines contains two integers $$$x_i,y_i$$$ ($$$-10^9 \le x_i,y_i \le 10^9$$$), the coordinates of the $$$i$$$-th vertex, listed in counterclockwise order.

Within a test case, all vertices are distinct. Adjacent edges intersect only at their shared endpoint, and nonadjacent edges do not intersect.

The sum of $$$n$$$ over all test cases does not exceed $$$10^5$$$.

Output

For each test case, output one integer: the number of stable directions.

Example
Input
3
4
0 0
1 0
2 1
1 1
4
0 0
2 0
2 2
0 2
6
0 0
4 0
4 1
1 1
3 4
0 4
Output
3
4
1
Note

The lines and stable directions for test case 1 are

$$$$$$ \begin{aligned} L_1:\quad &x-1=0, &\alpha_1&=0,\\ L_2:\quad &\frac{\sqrt{2}}{2}x+\frac{\sqrt{2}}{2}y-\frac{3\sqrt{2}}{4}=0, &\alpha_2&=\frac{\pi}{4},\\ L_3:\quad &-\frac{1}{\sqrt{5}}x+\frac{2}{\sqrt{5}}y=0, &\alpha_3&=\pi-\arctan 2. \end{aligned} $$$$$$

The lines and stable directions for test case 2 are

$$$$$$ \begin{aligned} L_1:\quad &x-1=0, &\alpha_1&=0,\\ L_2:\quad &y-1=0, &\alpha_2&=\frac{\pi}{2},\\ L_3:\quad &\frac{\sqrt{2}}{2}x+\frac{\sqrt{2}}{2}y-\sqrt{2}=0, &\alpha_3&=\frac{\pi}{4},\\ L_4:\quad &-\frac{\sqrt{2}}{2}x+\frac{\sqrt{2}}{2}y=0, &\alpha_4&=\frac{3\pi}{4}. \end{aligned} $$$$$$

The line and stable direction for test case 3 are

$$$$$$ L:\quad x-\frac{1}{2}=0, \qquad \alpha_1=0. $$$$$$

The corresponding line is not uniquely determined.