B. Сжатие массива и НОД
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Ashish есть массив $$$a$$$, состоящий из $$$2n$$$ положительных целых чисел. Он хочет сжать массив $$$a$$$ в массив $$$b$$$ размера $$$n-1$$$. Чтобы это сделать, он сначала выбирает ровно $$$2$$$ (любые два) элемента массива $$$a$$$ и удаляет их из массива. После этого он выполняет следующую операцию, пока массив $$$a$$$ не пустой:

  • удалить любые два элемента из массива $$$a$$$ и добавить их сумму в массив $$$b$$$.

Получившийся массив $$$b$$$ должен удовлетворять одному условию. Наибольший общий делитель ($$$\mathrm{gcd}$$$) всех элементов массива должен быть больше $$$1$$$.

Напомним, что наибольший общий делитель ($$$\mathrm{gcd}$$$) массива положительных целых чисел равен наибольшему целому числу, которое является делителем всех элементов массива.

Можно доказать, что всегда можно таким образом сжать массив $$$a$$$ в массив $$$b$$$ размера $$$n-1$$$, так что $$$gcd(b_1, b_2..., b_{n-1}) > 1$$$.

Помогите Ashish найти способ это сделать.

Входные данные

В первой строке находится единственное целое число $$$t$$$ ($$$1 \leq t \leq 10$$$)  — количество наборов входных данных. Описание наборов входных данных следует.

В первой строке описания каждого набора входных данных находится единственное целое число $$$n$$$ ($$$2 \leq n \leq 1000$$$).

Во второй строке описания каждого набора входных данных находится $$$2n$$$ целых чисел $$$a_1, a_2, \ldots, a_{2n}$$$ ($$$1 \leq a_i \leq 1000$$$)  — элементы массива $$$a$$$.

Выходные данные

Для каждого набора входных данных, выведите $$$n-1$$$ строку  — выполненные операции, чтобы сжать массив $$$a$$$ в массив $$$b$$$. Изначальное удаление двух элементов не является операцией и про это действие не нужно ничего выводить.

В $$$i$$$-й из этих строк должно находиться два целых числа, индексы (нумерация с $$$1$$$) двух элементов массива $$$a$$$, которые используются в $$$i$$$-й операции. Все $$$2n-2$$$ выведенных индекса должны быть различными целыми числами от $$$1$$$ до $$$2n$$$.

Вам не нужно выводить индексы двух изначально удаленных элементов из массива $$$a$$$.

Если есть несколько возможных ответов, вы можете найти любой.

Пример
Входные данные
3
3
1 2 3 4 5 6
2
5 7 9 10
5
1 3 3 4 5 90 100 101 2 3
Выходные данные
3 6
4 5
3 4
1 9
2 3
4 5
6 10
Примечание

В первом наборе входных данных $$$b = \{3+6, 4+5\} = \{9, 9\}$$$ и $$$\mathrm{gcd}(9, 9) = 9$$$.

Во втором наборе входных данных $$$b = \{9+10\} = \{19\}$$$ и $$$\mathrm{gcd}(19) = 19$$$.

В третьем наборе входных данных $$$b = \{1+2, 3+3, 4+5, 90+3\} = \{3, 6, 9, 93\}$$$ и $$$\mathrm{gcd}(3, 6, 9, 93) = 3$$$.