A. GCD Sort
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a permutation $$$p$$$ of integers from $$$1$$$ to $$$n$$$. In one operation, you can select two indices $$$i$$$ and $$$j$$$ $$$(1 \leq i, j \leq n)$$$ such that $$$\operatorname{gcd}(p_i, p_j) = 1$$$ and swap the elements at those indices. Here, $$$\operatorname{gcd}(x, y)$$$ denotes the greatest common divisor of $$$x$$$ and $$$y$$$.

You need to sort the permutation $$$p$$$ into ascending order using at most $$$2 \cdot n$$$ operations. Print the number of operations and the sequence of swaps needed to sort the permutation.

Input

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

For each test case, the first line contains an integer $$$n$$$ $$$(1 \le n \le 10^5)$$$ — the length of the permutation and the second line contains $$$n$$$ integers $$$p_1, p_2, \ldots, p_n$$$ — a permutation of integers from $$$1$$$ to $$$n$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$3 \cdot 10^5$$$.

Output

For each test case, in the first line, print an integer $$$x$$$ $$$(0 \le x \le 2 \cdot n)$$$, the number of operations performed. Then, print $$$x$$$ lines, each containing two integers $$$i$$$ and $$$j$$$ $$$(1 \leq i, j \leq n)$$$, which indicates a swap between the $$$i$$$-th and $$$j$$$-th elements of $$$p$$$.

If there are multiple ways to achieve the result, print any valid sequence of operations. It can be shown that a solution always exists under the given constraints. Note that you do not have to minimize the number of operations.

Example
Input
5
5
3 1 2 5 4
3
3 2 1
6
6 2 5 1 3 4
4
1 2 3 4
7
5 2 4 3 1 6 7
Output
3
4 5
1 2
2 3
3
2 3
1 3
1 2
7
3 5
1 4
4 5
3 6
6 4
5 6
3 4
0
2
1 5
3 4
Note

In the third test case,

  • Initial permutation: $$$[6, 2, 5, 1, 3, 4]$$$
  • Swap $$$p_3$$$ and $$$p_5$$$: $$$[6, 2, 3, 1, 5, 4]$$$
  • Swap $$$p_1$$$ and $$$p_4$$$: $$$[1, 2, 3, 6, 5, 4]$$$
  • Swap $$$p_4$$$ and $$$p_5$$$: $$$[1, 2, 3, 5, 6, 4]$$$
  • Swap $$$p_3$$$ and $$$p_6$$$: $$$[1, 2, 4, 5, 6, 3]$$$
  • Swap $$$p_6$$$ and $$$p_4$$$: $$$[1, 2, 4, 3, 6, 5]$$$
  • Swap $$$p_5$$$ and $$$p_6$$$: $$$[1, 2, 4, 3, 5, 6]$$$
  • Swap $$$p_3$$$ and $$$p_4$$$: $$$[1, 2, 3, 4, 5, 6]$$$

So we sorted the permutation using $$$7$$$ swaps which is under the limit of $$$2 \cdot n = 2 \cdot 6 = 12$$$ swaps.

In the fourth test case, the permutation is already sorted so no swaps are needed.