You are given $$$n$$$ points $$$(x_i, y_i)$$$ on a 2D plane, where $$$n$$$ is even. Select $$$\tfrac{n}{2}$$$ disjoint pairs $$$(a_i, b_i)$$$ to maximize the sum of Manhattan distances between points in pairs. In other words, maximize $$$$$$\sum_{i=1}^{n/2} |x_{a_i} - x_{b_i}| + |y_{a_i} - y_{b_i}|.$$$$$$

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

The first line of each test case contains a single even integer $$$n$$$ ($$$2 \leq n \leq 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^6 \le x_i, y_i \le 10^6$$$) — the coordinates of the $$$i$$$-th point.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output

For each test case, output $$$\tfrac{n}{2}$$$ lines, the $$$i$$$-th line containing two integers $$$a_i$$$ and $$$b_i$$$ — the indices of points in the $$$i$$$-th pair.

If there are multiple solutions, print any of them.

Note

In the first test case, an optimal solution is to select the pairs $$$(1, 4)$$$ and $$$(2, 3)$$$, which achieves a distance sum of $$$5 + 3 = 8$$$.

In the second test case, an optimal solution is to select the pairs $$$(1, 8)$$$, $$$(9, 10)$$$, $$$(5, 7)$$$, $$$(2, 3)$$$, $$$(4, 6)$$$, which achieves a distance sum of $$$4 + 7 + 10 + 5 + 7 = 33$$$.

Manhattan Pairs

Examples