A15450 | Parity Shuffle Sorting

You are given an array $a$ with $n$ non-negative integers. You can apply the following operation on it.

- Choose two indices $l$ and $r$ ( $1 \le l < r \le n$ ).
- If $a_l + a_r$ is odd, do $a_r := a_l$ . If $a_l + a_r$ is even, do $a_l := a_r$ .

Find any sequence of at most $n$ operations that makes $a$ non-decreasing. It can be proven that it is always possible. Note that you do not have to minimize the number of operations.

An array $a_1, a_2, \ldots, a_n$ is non-decreasing if and only if $a_1 \le a_2 \le \ldots \le a_n$ .

The first line contains one integer $t$ ( $1 \le t \le 10^5$ ) — the number of test cases.

Each test case consists of two lines. The first line of each test case contains one integer $n$ ( $1 \le n \le 10^5$ ) — the length of the array.

The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ( $0 \le a_i \le 10^9$ ) — the array itself.

It is guaranteed that the sum of $n$ over all test cases doesn't exceed $10^5$ .

For each test case, print one integer $m$ ( $0 \le m \le n$ ), the number of operations, in the first line.

Then print $m$ lines. Each line must contain two integers $l_i, r_i$ , which are the indices you chose in the $i$ -th operation ( $1 \le l_i < r_i \le n$ ).

If there are multiple solutions, print any of them.