As you are a master of sorting, you are often challenged by passing tourists to sort sequences using strange operations.

Because you are a renowned master of sorting, a novice from a neighboring country, Little I, came to visit you and left behind a permutation $a_1, a_2, \dots, a_n$ of length $n$, requesting that you sort it in ascending order using the following operation:

• Choose $i, j$ such that $1 \le i, j \le n$ and $|j - i| > 1$, and swap $a_i$ and $a_j$.

As a master of sorting known for your pursuit of perfection, you need to provide a sorting scheme that minimizes the number of operations, or report that it is impossible to sort the sequence using the given operation. If there are multiple schemes with the minimum number of operations, you may output any one of them.

Input

Read data from standard input.

This problem contains multiple test cases. The first line contains an integer $T (T \ge 1)$ representing the number of test cases.

For each test case, the first line contains an integer $n (1 \le n \le 10^{5})$ representing the length of the permutation. The next line contains $n$ distinct integers $a_1, a_2, \dots, a_n (1 \le a_i \le n)$ representing the given permutation.

It is guaranteed that the sum of $n$ over all test cases in a single test file does not exceed $10^{5}$.

Output

Output to standard output.

For each test case, if it is impossible to sort the sequence using the given operation, output a single integer -1. Otherwise, output an integer $s$ on the first line representing the minimum number of operations, followed by $s$ lines each containing two integers $i, j$, representing one operation. You must ensure $1 \le i, j \le n$ and $|j - i| > 1$.

It can be proven that for all possible inputs, if the sequence can be sorted using the given operations, then $s \le 5n$.

Examples

Input 1

2
4
2 3 4 1
2
2 1

Output 1

5
2 4
1 4
1 3
2 4
1 4
-1

Note 1

For the first test case, the sorting process is $2341 \to 2143 \to 3142 \to 4132 \to 4231 \to 1234$. It can be proven that no scheme with fewer steps exists.