Hockey
After the disappointing performance of the Russian hockey team in Vancouver, everyone seemed to have an opinion on what went wrong. Some criticized the Russian players for lacking determination, while others praised the Canadians for their intense focus. Russian hockey officials also suggested that the size of the Canadian rinks, which differ significantly from the European ones, played a major role in the defeat. To prepare for a comeback at the next Olympics in Sochi, it was decided to surprise the Canadians with "Russian" rinks.
A Russian hockey rink is shaped like a convex polygon. On such a rink, the Russians are confident they can defeat both the Canadians and any other team. However, the builders encountered a challenge in marking out this rink. They first needed to draw the central line. It was decided that this line should pass through two vertices of the polygon and divide the rink into two "half-polygons" such that the ratio of the area of the smaller "half-polygon" to the area of the larger one is as close as possible to 1, or exactly 1.
Your task is to assist the builders in finding this central line.
Input
The first line contains an integer T – the number of test cases (1 ≤ T ≤ 10). Each test case begins with the number N – the number of vertices of the polygon (4 ≤ N ≤ 2000), followed by N lines, each containing two integers representing the coordinates of the polygon's vertices. The coordinates do not exceed 10000 in absolute value.
Output
For each test case, output two lines. The first line should contain two numbers – the indices of the vertices through which the dividing diagonal is drawn. These indices must be in ascending order. The numbering starts from 1 and corresponds to the order of the vertices in the input data. The second line should display the correct irreducible fraction representing the ratio of the areas. If there are multiple correct solutions, choose the one with the smallest index for the first vertex. If there is still a tie, choose the solution with the smallest index for the second vertex.