Problem Statement

There are $N$ stars on the $xy$-plane. The $i$-th star is represented as the point with coordinates $(X_i,Y_i)$.

Draw one line that passes through the origin and does not pass through any star, and choose one of the two regions into which the line divides the plane.

Find the maximum possible number of stars contained in the chosen region.

You are given $T$ test cases; solve each of them.

Constraints

• $1 \le T \le 2 \times 10^5$
• $1 \le N \le 2 \times 10^5$
• The sum of $N$ over all test cases is at most $2 \times 10^5$.
• $-10^9 \le X_i,Y_i \le 10^9$
• $(X_i,Y_i) \ne (0,0)$
• $(X_i,Y_i) \ne (X_j, Y_j) ~ (i \ne j)$
• No two distinct stars are collinear with the origin.
• All input values are integers.

Input

The input is given from Standard Input in the following format:

T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T

Each test case is given in the following format:

N
X_1 Y_1
X_2 Y_2
\vdots
X_N Y_N

Output

Print $T$ lines. The $i$-th line should contain the answer for the $i$-th test case.