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$.


-----Input-----

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$.


-----Output-----

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.


-----Examples-----

Input
3
2
7 8
5
1 1000000000 3 0 5
1
0
Output
0
2
3 4
1 2
0


-----Note-----

In the second test case, $a$ changes like this:

Select indices $3$ and $4$. $a_3 + a_4 = 3$ is odd, so do $a_4 := a_3$. $a = [1, 1000000000, 3, 3, 5]$ now.

Select indices $1$ and $2$. $a_1 + a_2 = 1000000001$ is odd, so do $a_2 := a_1$. $a = [1, 1, 3, 3, 5]$ now, and it is non-decreasing.

In the first and third test cases, $a$ is already non-decreasing.

Source: codeforces | Difficulty: EASY
Tags: Sorting

Constructive algorithms


Solutions:
import sys
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	if a == sorted(a):
		print(0)
		continue
	m = 0
	ans = []
	p = a[0] & 1
	l = -1
	li = -1
	for i in range(n - 1, -1, -1):
		if a[i] & 1 == p:
			if l == -1:
				l = a[i]
				li = i
			elif a[i] > l:
				a[i] = l
				m += 1
				ans.append([i + 1, li + 1])
			else:
				l = a[i]
				li = i
	t = 0
	for i in range(1, n):
		if a[i] & 1 != p:
			m += 1
			ans.append([t + 1, i + 1])
		else:
			t = i
	print(m)
	for i in ans:
		print(*i)