cat

The cat Motanel’s favourite activity is sorting. She generally has a row of $N$ blocks in front of her, of distinct sizes, and she tries to sort these in increasing order of size, by using a sequence of swaps. Since cat’s like pairing things, $N$ is even. Unfortunately, the dastardly rat Sobo, tries to trick Motanel, and, each time Motanel swaps the $i^{\text{th}}$ block and the $j^{\text{th}}$ block, Sobo will then swap the blocks on positions $(N-i+1)$ and $(N-j+1)$. How can Motanel optimally sort the blocks ?

More formally, you are given a permutation $P_1, P_2, \dots, P_N$. An operation on indices $(i, j)$ is defined to swap $P_i$ and $P_j$ , and then to swap $P_{N-i+1}$ and $P_{N-j+1}$.

Task

Given $N$ and $P$, create a minimal sequence of operations that sorts $P$.

Input data

There will be multiple test cases in each input file.

On the first line of the input there will be an integer that represents the number of test cases in this file.

On the first line of each test case there will be an integer that represents the value of $N$.

On the next line of each test case will follow 𝑁 integers, that represent $P_1, P_2, \dots P_N$ respectively.

Output data

Output the answers to the $T$ test cases in order.

If there is no way of sorting the permutation, simply print $-1$ on a new line.

Otherwise, begin by outputting a line that contains two integers $g$ and $L$, which represent the length that you think a minimal sequence of operations has, and the length that your sequence of operations has (for partial points, these can be different). Then continue by outputting $L$ further lines, each of which will contain two integers $i$ and $j$. Such a line represents an operation on indices $(i,j)$. Note you may choose to let $L = 0$ if you don’t aim at scoring the reconstruction points, for more details see section Scoring. You’ll get $0$ points on the subtask of a test if you ever print a negative $L$, or make an invalid move. An invalid move $(i,j)$ either has $i = j$ or one of the positions out of the range $[1, N]$.

Restrictions

In all tests, $2 \leq N \leq 200 \ 000$, $N$ is even and $P$ is a permutation: any value between $1$ and $N$ appears exactly once in $P$.

Scoring

Each subtask will be scored independently. The score you’ll get is the score assigned to the subtask multiplied with the minimum ratio among all tests of that subtask. The ratio of a test is computed as follows:

• If there is any subtest where you haven’t properly decided whether a solution exists or not, then the ratio is $0$
• If you’ve made throughout the whole test more than $3 \cdot 10^6$ moves, the ratio is $0$
• If you’ve given a correct optimal reconstruction of moves for all subtests inside the test, the ratio for that test is $1.0$ (regardless of whether your guess of optimal length was correct)
• If you’ve computed the correct optimal number of moves and gave a correct, solution for all subtests inside the test, the ratio for that test is $0.7$
• If you’ve computed the correct optimal number of moves, the ratio is $0.4$
• If you’ve given a correct reconstruction of moves for every subtest that was solvable, the ratio is $0.35$
• If you have at least one wrong reconstruction for a subtest, provided you’ve correctly distinguished between when you can sort the permutation and when you can’t, the ratio for the test is $0.15$

Assume these criteria are considered in this exact order and the coefficient is given by the first condition that matches the case of the current test.

Example

stdin

4
6
2 6 4 3 1 5
10
4 9 6 3 1 10 8 5 2 7
4
4 1 3 2
10
7 8 9 10 5 6 1 2 3 4

stdout

3 3
2 4
2 3
1 2
5 5
2 8
2 5
1 4
1 3
1 2
-1
2 2
2 8
1 7