Little Cyan Fish tiene una permutación $p_1, p_2, \ldots, p_n$ de los enteros del $1$ al $n$ y, como sugiere el título del problema, quiere ordenarla en orden ascendente. Esta vez, la operación que puede realizar es la siguiente.

• En una operación, Little Cyan Fish puede elegir dos enteros $i$ y $j$ tales que $1 \le i < j \le n$ e intercambiar $p_i$ y $p_j$.

Pero, vamos, todo el mundo sabe cómo ordenar una permutación con intercambios simples, así que obviamente esto no es lo que el problema te pide hacer. En su lugar, Little Cyan Fish define la distancia de una operación como $j - i$. Para una secuencia de operaciones que ordena la permutación, sea $a_d$ el número de operaciones de distancia $d$, para cada $1 \le d < n$.

Entre todas las secuencias finitas de operaciones que ordenan la permutación, Little Cyan Fish quiere que encuentres la secuencia $(a_1, a_2, \ldots, a_{n-1})$ lexicográficamente más pequeña, y construyas una secuencia de a lo sumo $5n$ operaciones que la logre.

Entrada

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

Para cada caso de prueba, la primera línea contiene un solo entero $n$ ($2 \le n \le 10^6$), que indica la longitud de la permutación. La segunda línea contiene $n$ enteros $p_1, p_2, \ldots, p_n$ ($1 \le p_i \le n$), que indican la permutación. Se garantiza que $p$ es una permutación de longitud $n$.

Se garantiza que la suma de $n$ en todos los casos de prueba no supera $10^6$.

Salida

Para cada caso de prueba, imprime la respuesta en el siguiente formato.

La primera línea de cada caso de prueba debe contener $n - 1$ enteros $a_1, a_2, \ldots, a_{n-1}$, la secuencia lexicográficamente más pequeña.

La segunda línea debe contener un solo entero $k$ ($0 \le k \le 5n$), el número de operaciones en tu secuencia.

Cada una de las siguientes $k$ líneas debe contener dos enteros $i$ y $j$ ($1 \le i < j \le n$), los índices elegidos en la operación correspondiente. Las operaciones, realizadas en el orden dado, deben ordenar la permutación de entrada, y para cada $1 \le d < n$, exactamente $a_d$ de las operaciones deben tener distancia $d$.

Se puede demostrar que siempre existe una secuencia óptima de a lo sumo $5n$ operaciones. Si hay múltiples secuencias de operaciones válidas, puedes imprimir cualquiera de ellas.

Ejemplos

Entrada 1

3
3
3 2 1
4
2 1 3 4
4
1 3 2 4

Salida 1

0 1
1
1 3
0 1 2
3
1 4
2 4
1 4
0 3 2
5
1 3
1 4
2 4
1 4
1 3

Nota

En el primer caso de prueba de ejemplo, Little Cyan Fish intercambia las posiciones $1$ y $3$. Esto ordena la permutación usando una operación de distancia $2$.

En el segundo caso de prueba de ejemplo, una secuencia óptima es $(1, 4)$, $(2, 4)$, $(1, 4)$. Las distancias son $3$, $2$ y $3$, por lo que la secuencia resultante es $(0, 1, 2)$.

En el tercer caso de prueba de ejemplo, una secuencia óptima es $(2, 4)$, $(1, 4)$, $(1, 3)$, $(1, 4)$, $(2, 4)$. Sus conteos de distancias son $(0, 3, 2)$.