B. Convex Interval
time limit per test
3 s
memory limit per test
512 megabytes
input
standard input
output
standard output

You are given a list of $$$n$$$ pairwise distinct points $$$p_1, p_2, \dots, p_n$$$ on a 2D plane. An interval $$$[l, r]$$$ of points is called convex if the following conditions hold:

  • the length of the interval ($$$r - l + 1$$$) is at least $$$3$$$;
  • the points $$$p_l, p_{l+1}, \dots, p_r$$$ in this order form a strictly convex polygon written out in a clockwise order.

Recall that a strictly convex polygon is a convex polygon that has no three consecutive points on the same line.

Find the maximum length of a convex interval in the given list. If there are no convex intervals, print $$$0$$$.

Input

The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.

The first line of each test case contains a single integer $$$n$$$ ($$$3 \le n \le 2 \cdot 10^5$$$) — the number of points.

The $$$i$$$-th of the next $$$n$$$ lines contains two integers $$$x_i$$$ and $$$y_i$$$ ($$$-10^9 \le x_i, y_i \le 10^9$$$) — the coordinates of the point $$$p_i$$$.

Additional constraints on the input:

  • the sum of $$$n$$$ over all test cases doesn't exceed $$$2 \cdot 10^5$$$;
  • in each test case, the points are pairwise distinct (if $$$i \neq j$$$, either $$$x_i \neq x_j$$$ or $$$y_i \neq y_j$$$ holds).
Output

For each test case, print a single integer — the maximum length of a convex interval in the given list of points.

Example
Input
3
5
0 0
0 2
1 1
2 2
2 0
7
-4 5
-7 5
-4 8
-1 9
6 3
7 -5
4 4
6
-1 0
0 0
1 1
1 -1
0 1
1 0
Output
3
5
3