Problem
You have an array �A with �N elements.
You can perform the following operation at most 20×�20×N times:
- Select two indices �,�i,j satisfying ��≠��Ai=Aj, and set both ��Ai and ��Aj to ��⊕��Ai⊕Aj.
Here, ⊕⊕ denotes the bitwise XOR operation.
Your goal is to make the final array sorted in non-decreasing order. Find a sequence of operations that achieves this.
It can be proven that a solution always exists.
Note that you don’t have to minimize the number of operations.
Input Format
- The first line contains a single integer �T, denoting the number of test cases. Then the test cases follow.
- Each test case consists of two lines of input.
- The first line of each test case contains an integer �N — the size of the array �A.
- The second line contains �N space-separated integers �1,�2,…,��A1,A2,…,AN.
Output Format
- For each test case, first print a single integer �K, the number of operations you performed.
- Then, print �K lines each containing two integers. The integers on the �i-th line should be the indices you selected for the �i-th operation.
Constraints
- 1≤�≤1041≤T≤104
- 1≤�≤1051≤N≤105
- 0≤��≤1090≤Ai≤109
- The sum of �N over all test cases won’t exceed 105105.
Sample 1:
Input
Output
2 4 34 40 20 30 3 1 2 3
2 1 4 1 3 0
Explanation:
Test case 11:
- The array becomes [60,40,20,60][60,40,20,60] after the first operation. (Setting �1A1 and �4A4 to 34⊕3034⊕30)
- The array becomes [40,40,40,60][40,40,40,60] after the second operation. (Setting �1A1 and �3A3 to 60⊕2060⊕20)
Test case 22:
- The array is already sorted, so we don’t need to perform any operations.
Solution:
