You are given a permutation of size N. You want to sort it. In one operation you can swap the i^th and the j^th elements (1 ≤ i, j ≤ N) and it will cost you i&j *(bitwise *AND of i and j). Total sum of sorting the permutation is the sum of the cost of all the operations you will make. You can’t make more than 3*N operations. Print the minimum cost to sort the permutation and also print one sequence of swap operations which will sort the permutation in the minimum cost.

The first line will contain a single integer T (1 ≤ T ≤ 10⁴). Each test case will start with one integer N (1 ≤ N ≤ 10⁴), the length of the permutation. The next line will contain N integers a₁, a₂, …. , a_N (1 ≤ a_i ≤ N). It is guaranteed that, in any input file $\sum$N ≤ 10⁵ across all the test cases.

Input file is large. Please be sure to use faster input/output methods.

For each test case, the first line of the output should contain the minimum cost to sort the array. The next line should contain the number of required operations. Then each next line should contain two integers describing the indices being swapped. Please see the sample for details.

Permutation of size N is an array of size N where each number from 1…N appears exactly once. i&j denotes bitwise AND between integer i and integer j.

Contest: NCPC 2023 Onsite Hosted by JU

Problem setter: Arghya Pal