A. Alalay
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

The Autonomous Municipal Government of Cochabamba has decided to build a park around the Alalay Lagoon. El Soto, after working for 2 years on a cargo ship, has decided to work for the municipality. He studied physics, but they made him pass as a civil engineer since El Soto can handle everything. El Soto provided a list of points to Samir, the geometry manager of the municipality. El Soto claimed that the supposed list of points is ordered counterclockwise and that it forms the convex hull enclosing the lagoon. El Soto also claims that this convex hull would be a good boundary for the park according to mathematical calculations that El Soto is capable of doing in his head and that you wouldn't understand.

The convex hull is defined as the smallest convex polygon that can enclose a set of points in the plane.

Samir looks at him doubtfully and discovers that El Soto was mistaken, but not entirely; the coordinates are correct, but their order is not. He realizes that by swapping two coordinates, he can fix the plan and obtain a counterclockwise convex hull. Help El Soto and Samir figure out which coordinates to swap.

Input

The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 10^4$$$) representing the number of test cases.

For each test case, the first line contains an integer $$$n$$$ ($$$4 \leq n \leq 10^5$$$) representing the number of points in the order that El Soto provided to Samir.

The following $$$n$$$ lines each contain two integers $$$x_i$$$ and $$$y_i$$$ ($$$-10^9 \leq x_i, y_i \leq 10^9$$$) representing the coordinates of the points.

It is guaranteed that the sum of $$$n$$$ across all test cases does not exceed $$$10^5$$$, that in each test case there are no three collinear points, and that for each test case there is always a unique solution.

Output

For each test case, print two integers $$$i$$$, $$$j$$$ $$$(i \lt j)$$$, the indices of the coordinates that need to be swapped to obtain a correctly ordered convex hull.

Example
Input
2
4
0 0
1 1
1 0
0 1
5
1 0
4 3
3 0
2 5
0 2
Output
2 3
2 3