En el año 2077, crear problemas se vuelve sencillo. Los robots generarán un problema estableciendo algunas operaciones aleatorias y luego lo resolverán. Quien propone el problema solo tiene que comprobar si el problema es correcto o no.

Aquí hay un problema del año 2077:

Dada una permutación $p_1, p_2, \dots, p_n$, se garantiza que $n$ es par. Deseas ordenar la permutación usando únicamente un tipo de operación:

• FakeSort(l,r): Debes garantizar que $r - l + 1$ sea par. Sea $k = r - l + 1$; entonces los $k/2$ elementos más grandes y los $k/2$ elementos más pequeños de la subsecuencia continua $p_l, p_{l+1}, \dots, p_r$ se ordenarán de forma independiente. Es decir, sean $L_1, L_2, \dots, L_{k/2}$ los índices de los $k/2$ números más grandes, y $S_1, S_2, \dots, S_{k/2}$ los índices de los $k/2$ números más pequeños. Primero ordenamos los números en los índices $L_1 \sim L_{k/2}$, y luego ordenamos los números en los índices $S_1 \sim S_{k/2}$.

Aquí tienes un ejemplo concreto; supongamos que la permutación es $p = \{2, 5, 7, 1, 8, 6, 4, 3\}$. Si llamamos a FakeSort(2,7):

• $k = r - l + 1 = 6$. La subsecuencia continua $p_l, p_{l+1}, \dots, p_r$ es $\{5, 7, 1, 8, 6, 4\}$; ordenaremos los $3$ números más grandes y los $3$ números más pequeños de esta secuencia de forma independiente.
• $p = \{2, 5, \mathbf{7}, 1, \mathbf{8}, \mathbf{6}, 4, 3\}$; los $3$ números más grandes están en negrita. Después de ordenarlos, quedan como $p = \{2, 5, \mathbf{6}, 1, \mathbf{7}, \mathbf{8}, 4, 3\}$.
• $p = \{2, \mathbf{5}, 6, \mathbf{1}, 7, 8, \mathbf{4}, 3\}$; los $3$ números más pequeños están en negrita. Después de ordenarlos, quedan como $p = \{2, \mathbf{1}, 6, \mathbf{4}, 7, 8, \mathbf{5}, 3\}$.

Por lo tanto, $p = \{2, 5, 7, 1, 8, 6, 4, 3\}$ después de FakeSort(2,7) se convierte en $\{2, 1, 6, 4, 7, 8, 5, 3\}$.

Por favor, utiliza no más de $114$ operaciones para ordenar la permutación o determina que es imposible. Se puede demostrar que si una permutación se puede ordenar con esta operación, existe una manera de hacerlo usando no más de $114$ operaciones.

Entrada

La entrada contiene múltiples casos de prueba. La primera línea de la entrada contiene un entero $T$ ($1 \le T \le 10^3$), el número de casos de prueba.

Para cada caso de prueba, la primera línea contiene un entero par $n$ ($4 \le n \le 10^5$), la longitud de la permutación.

La segunda línea contiene $n$ enteros $p_1, p_2, \dots, p_n$ ($1 \le p_i \le n$), la permutación que necesitas ordenar. Se garantiza que $p$ es una permutación.

Se garantiza que la suma de $n$ en todos los casos de prueba no supera $2 \times 10^5$.

Salida

Para cada caso de prueba, si es imposible ordenar la permutación, imprime $-1$.

En caso contrario, imprime un entero $k$ ($0 \le k \le 114$), que indica el número de operaciones utilizadas.

En las siguientes $k$ líneas, imprime $l, r$ ($1 \le l \le r \le n$, $r - l + 1$ es par) en cada línea, indicando que se realiza FakeSort(l,r).

Ejemplos

Entrada de ejemplo 1

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

Salida de ejemplo 1

1
1 4
-1
2
4 7
1 6