Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official.
×

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

The problem statement has recently been changed. View the changes.

×
B. GCD Compression

time limit per test

1 secondmemory limit per test

256 megabytesinput

standard inputoutput

standard outputAshish has an array $$$a$$$ of consisting of $$$2n$$$ positive integers. He wants to compress $$$a$$$ into an array $$$b$$$ of size $$$n-1$$$. To do this, he first discards exactly $$$2$$$ (any two) elements from $$$a$$$. He then performs the following operation until there are no elements left in $$$a$$$:

- Remove any two elements from $$$a$$$ and append their sum to $$$b$$$.

The compressed array $$$b$$$ has to have a special property. The greatest common divisor ($$$\mathrm{gcd}$$$) of all its elements should be greater than $$$1$$$.

Recall that the $$$\mathrm{gcd}$$$ of an array of positive integers is the biggest integer that is a divisor of all integers in the array.

It can be proven that it is always possible to compress array $$$a$$$ into an array $$$b$$$ of size $$$n-1$$$ such that $$$gcd(b_1, b_2..., b_{n-1}) > 1$$$.

Help Ashish find a way to do so.

Input

The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 10$$$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$2 \leq n \leq 1000$$$).

The second line of each test case contains $$$2n$$$ integers $$$a_1, a_2, \ldots, a_{2n}$$$ ($$$1 \leq a_i \leq 1000$$$) — the elements of the array $$$a$$$.

Output

For each test case, output $$$n-1$$$ lines — the operations performed to compress the array $$$a$$$ to the array $$$b$$$. The initial discard of the two elements is not an operation, you don't need to output anything about it.

The $$$i$$$-th line should contain two integers, the indices ($$$1$$$ —based) of the two elements from the array $$$a$$$ that are used in the $$$i$$$-th operation. All $$$2n-2$$$ indices should be distinct integers from $$$1$$$ to $$$2n$$$.

You don't need to output two initially discarded elements from $$$a$$$.

If there are multiple answers, you can find any.

Example

Input

3 3 1 2 3 4 5 6 2 5 7 9 10 5 1 3 3 4 5 90 100 101 2 3

Output

3 6 4 5 3 4 1 9 2 3 4 5 6 10

Note

In the first test case, $$$b = \{3+6, 4+5\} = \{9, 9\}$$$ and $$$\mathrm{gcd}(9, 9) = 9$$$.

In the second test case, $$$b = \{9+10\} = \{19\}$$$ and $$$\mathrm{gcd}(19) = 19$$$.

In the third test case, $$$b = \{1+2, 3+3, 4+5, 90+3\} = \{3, 6, 9, 93\}$$$ and $$$\mathrm{gcd}(3, 6, 9, 93) = 3$$$.

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Sep/23/2021 16:04:48 (i1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|