Trilobite loves building subways. He has designed $n$ lines, each with $n+1$ potential station locations represented by coordinates on a plane.

To enrich the subway experience, Trilobite has decided that each line will be a line segment! That is, for each line, Trilobite will choose exactly two stations and connect them with a line segment. To maximize the inconvenience for passengers transferring, Trilobite requires that the number of intersections between any two of the $n$ subway lines be minimized. Note that intersections include the start and end stations. Please plan a valid scheme.

In plain terms: Given $n$ colors of points on a 2D plane, with $n+1$ points for each color. You are required to select two distinct points for each color to form a line segment, such that the total number of intersections between all $n$ line segments is minimized. Output the construction scheme.

Note: If two line segments are collinear, the number of intersections is defined as infinity. All infinities are considered equal.

Input

The input contains multiple test cases. The first line contains a positive integer $T$ representing the number of test cases. For each test case:

The first line contains a positive integer $n$, the number of lines.

The next $n$ lines each contain $2n+2$ integers, where the $j$-th station for the current line is represented by the $(2j-1)$-th and $(2j)$-th integers $(x_j, y_j)$ in the line, and the label of that station is $j$.

It is guaranteed that all station coordinates are distinct.

Output

For each test case, output $n$ lines, each containing two positive integers representing the labels of the two stations connected by each line. You only need to output any valid solution.

Examples

Input 1

1
2
5 0 0 8 10 8
0 4 10 4 5 12

Output 1

1 3
1 3

Note

In the figure, the blue and red points represent the stations for line 1 and line 2, respectively, and the blue and red lines represent the segments chosen for line 1 and line 2.

Note that you only need to output any valid solution, so:

1 2
2 3

is also a correct answer.

Constraints

For all data: $1\le n\le 1000, \sum n\leq 2000$, $|x_i|, |y_i|\le 10^9$.