C. Сортировка четностью
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дан массив $$$a$$$ из $$$n$$$ неотрицательных целых чисел. Вы можете применять на нём следующую операцию.

  • Выберите два индекса $$$l$$$ и $$$r$$$ ($$$1 \le l < r \le n$$$).
  • Если $$$a_l + a_r$$$ нечетно, то выполните $$$a_r := a_l$$$. Если $$$a_l + a_r$$$ четно, то выполните $$$a_l := a_r$$$.

Найдите любую последовательность из не более чем $$$n$$$ операций, которая делает массив $$$a$$$ неубывающим. Можно доказать, что она всегда существует. Обратите внимание, что вам не нужно минимизировать количество операций.

Массив $$$a_1, a_2, \ldots, a_n$$$ неубывающий тогда и только тогда, когда $$$a_1 \le a_2 \le \ldots \le a_n$$$.

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

Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 10^5$$$) — количество наборов входных данных.

Каждый набор входных данных состоит из двух строк. Первая строка каждого теста содержит одно целое число $$$n$$$ ($$$1 \le n \le 10^5$$$) — длина массива.

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le 10^9$$$) — сам массив.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$10^5$$$.

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

Для каждого набора входных данных выведите в первой строке одно целое число $$$m$$$ ($$$0 \le m \le n$$$) — количество операций.

Затем выведите $$$m$$$ строк. Каждая строка должна содержать два целых числа $$$l_i, r_i$$$, которые являются индексами, выбранными вами в $$$i$$$-й операции ($$$1 \le l_i < r_i \le n$$$).

Если решений несколько, выведите любое из них.

Пример
Входные данные
3
2
7 8
5
1 1000000000 3 0 5
1
0
Выходные данные
0
2
3 4
1 2
0
Примечание

Во втором примере $$$a$$$ изменяется следующим образом:

  • Выберите индексы $$$3$$$ и $$$4$$$. $$$a_3 + a_4 = 3$$$ нечетно, поэтому надо выполнить $$$a_4 := a_3$$$. После этого $$$a = [1, 1000000000, 3, 3, 5]$$$.
  • Выберите индексы $$$1$$$ и $$$2$$$. $$$a_1 + a_2 = 1000000001$$$ нечетно, поэтому надо выполнить $$$a_2 := a_1$$$. Теперь $$$a = [1, 1, 3, 3, 5]$$$ и массив неубывающий.

В первом и третьем примерах $$$a$$$ уже неубывающий.