Parity Shuffle Sorting solution codeforces

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𝑙<𝑟𝑛1≤l<r≤n).
  • If 𝑎𝑙+𝑎𝑟al+ar is odd, do 𝑎𝑟:=𝑎𝑙ar:=al. If 𝑎𝑙+𝑎𝑟al+ar is even, do 𝑎𝑙:=𝑎𝑟al:=ar.

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 𝑎1,𝑎2,,𝑎𝑛a1,a2,…,an is non-decreasing if and only if 𝑎1𝑎2𝑎𝑛a1≤a2≤…≤an.

Input

Parity Shuffle Sorting solution codeforces

The first line contains one integer 𝑡t (1𝑡1051≤t≤105) — the number of test cases.

Each test case consists of two lines. The first line of each test case contains one integer 𝑛n (1𝑛1051≤n≤105) — the length of the array.

The second line of each test case contains 𝑛n integers 𝑎1,𝑎2,,𝑎𝑛a1,a2,…,an (0𝑎𝑖1090≤ai≤109)  — the array itself.

It is guaranteed that the sum of 𝑛n over all test cases doesn’t exceed 105105.

Output

For each test case, print one integer 𝑚m (0𝑚𝑛0≤m≤n), the number of operations, in the first line.

Then print 𝑚m lines. Each line must contain two integers 𝑙𝑖,𝑟𝑖li,ri, which are the indices you chose in the 𝑖i-th operation (1𝑙𝑖<𝑟𝑖𝑛1≤li<ri≤n).

If there are multiple solutions, print any of them.

Example

input

Copy

3

Parity Shuffle Sorting solution codeforces

2
7 8
5
1 1000000000 3 0 5
1
0

output

Copy
0
2
3 4
1 2
0
Note

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

Parity Shuffle Sorting solution codeforces

  • Select indices 33 and 44𝑎3+𝑎4=3a3+a4=3 is odd, so do 𝑎4:=𝑎3a4:=a3𝑎=[1,1000000000,3,3,5]a=[1,1000000000,3,3,5] now.
  • Select indices 11 and 22𝑎1+𝑎2=1000000001a1+a2=1000000001 is odd, so do 𝑎2:=𝑎1a2:=a1𝑎=[1,1,3,3,5]a=[1,1,3,3,5] now, and it is non-decreasing.

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

Solution – CLICK HERE

Leave a Comment

Your email address will not be published.