Little Cyan Fish ha una permutazione $p_1, p_2, \ldots, p_n$ degli interi da $1$ a $n$ e, come suggerisce il titolo del problema, vuole ordinarla in ordine crescente. Questa volta, l'operazione che può eseguire è la seguente.

• In un'operazione, Little Cyan Fish può scegliere due interi $i$ e $j$ tali che $1 \le i < j \le n$ e scambiare $p_i$ e $p_j$.

Ma andiamo, tutti sanno come ordinare una permutazione con semplici scambi, quindi ovviamente non è questo ciò che il problema ti chiede di fare. Invece, Little Cyan Fish definisce la distanza di un'operazione come $j - i$. Per una sequenza di operazioni che ordina la permutazione, sia $a_d$ il numero di operazioni di distanza $d$, per ogni $1 \le d < n$.

Tra tutte le sequenze finite di operazioni che ordinano la permutazione, Little Cyan Fish vuole che tu trovi la sequenza $(a_1, a_2, \ldots, a_{n-1})$ lessicograficamente più piccola, e che costruisca una sequenza di al più $5n$ operazioni che la realizza.

Input

Ci sono più casi di test. La prima riga dell'input contiene un singolo intero $T$ ($1 \le T \le 10^6$), che indica il numero di casi di test.

Per ciascun caso di test, la prima riga contiene un singolo intero $n$ ($2 \le n \le 10^6$), che indica la lunghezza della permutazione. La seconda riga contiene $n$ interi $p_1, p_2, \ldots, p_n$ ($1 \le p_i \le n$), che indicano la permutazione. È garantito che $p$ è una permutazione di lunghezza $n$.

È garantito che la somma di $n$ su tutti i casi di test non supera $10^6$.

Output

Per ciascun caso di test, stampa la risposta nel seguente formato.

La prima riga di ciascun caso di test deve contenere $n - 1$ interi $a_1, a_2, \ldots, a_{n-1}$, la sequenza lessicograficamente più piccola.

La seconda riga deve contenere un singolo intero $k$ ($0 \le k \le 5n$), il numero di operazioni nella tua sequenza.

Ciascuna delle successive $k$ righe deve contenere due interi $i$ e $j$ ($1 \le i < j \le n$), gli indici scelti nell'operazione corrispondente. Le operazioni, eseguite nell'ordine dato, devono ordinare la permutazione in input e, per ogni $1 \le d < n$, esattamente $a_d$ operazioni devono avere distanza $d$.

Si può dimostrare che esiste sempre una sequenza ottimale di al più $5n$ operazioni. Se esistono più sequenze di operazioni valide, puoi stamparne una qualsiasi.

Esempi

Input 1

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

Output 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

Nel primo caso di test di esempio, Little Cyan Fish scambia le posizioni $1$ e $3$. Questo ordina la permutazione usando un'operazione di distanza $2$.

Nel secondo caso di test di esempio, una sequenza ottimale è $(1, 4)$, $(2, 4)$, $(1, 4)$. Le distanze sono $3$, $2$ e $3$, quindi la sequenza risultante è $(0, 1, 2)$.

Nel terzo caso di test di esempio, una sequenza ottimale è $(2, 4)$, $(1, 4)$, $(1, 3)$, $(1, 4)$, $(2, 4)$. I conteggi delle sue distanze sono $(0, 3, 2)$.