Little Cyan Fish har en permutasjon $p_1, p_2, \ldots, p_n$ av heltallene fra $1$ til $n$, og som tittelen på oppgaven antyder, ønsker han å sortere den i stigende rekkefølge. Denne gangen er operasjonen han kan utføre som følger.

• I én operasjon kan Little Cyan Fish velge to heltall $i$ og $j$ slik at $1 \le i < j \le n$ og bytte plass på $p_i$ og $p_j$.

Men kom igjen, alle vet hvordan man sorterer en permutasjon med enkle bytter, så dette er åpenbart ikke det oppgaven ber deg om å gjøre. I stedet definerer Little Cyan Fish avstanden til en operasjon som $j - i$. For en sekvens av operasjoner som sorterer permutasjonen, la $a_d$ betegne antallet operasjoner med avstand $d$, for hver $1 \le d < n$.

Blant alle endelige sekvenser av operasjoner som sorterer permutasjonen, vil Little Cyan Fish at du skal finne den leksikografisk minste sekvensen $(a_1, a_2, \ldots, a_{n-1})$, og konstruere en sekvens med høyst $5n$ operasjoner som oppnår den.

Inndata

Det er flere testtilfeller. Den første linjen i inndataene inneholder et enkelt heltall $T$ ($1 \le T \le 10^6$), som angir antallet testtilfeller.

For hvert testtilfelle inneholder den første linjen et enkelt heltall $n$ ($2 \le n \le 10^6$), som angir lengden på permutasjonen. Den andre linjen inneholder $n$ heltall $p_1, p_2, \ldots, p_n$ ($1 \le p_i \le n$), som angir permutasjonen. Det er garantert at $p$ er en permutasjon av lengde $n$.

Det er garantert at summen av $n$ over alle testtilfeller ikke overstiger $10^6$.

Utdata

For hvert testtilfelle skal du skrive ut svaret i følgende format.

Den første linjen for hvert testtilfelle skal inneholde $n - 1$ heltall $a_1, a_2, \ldots, a_{n-1}$, den leksikografisk minste sekvensen.

Den andre linjen skal inneholde et enkelt heltall $k$ ($0 \le k \le 5n$), antallet operasjoner i sekvensen din.

Hver av de følgende $k$ linjene skal inneholde to heltall $i$ og $j$ ($1 \le i < j \le n$), indeksene som er valgt i den tilsvarende operasjonen. Operasjonene, utført i den oppgitte rekkefølgen, må sortere inndatapermutasjonen, og for hver $1 \le d < n$ må nøyaktig $a_d$ av operasjonene ha avstand $d$.

Det kan vises at en optimal sekvens med høyst $5n$ operasjoner alltid eksisterer. Hvis det finnes flere gyldige sekvenser av operasjoner, kan du skrive ut hvilken som helst av dem.

Eksempler

Inndata 1

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

Utdata 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

Forklaring

I det første eksempeltesttilfellet bytter Little Cyan Fish plass på posisjonene $1$ og $3$. Dette sorterer permutasjonen ved hjelp av én operasjon med avstand $2$.

I det andre eksempeltesttilfellet er én optimal sekvens $(1, 4)$, $(2, 4)$, $(1, 4)$. Avstandene er $3$, $2$ og $3$, så den resulterende sekvensen er $(0, 1, 2)$.

I det tredje eksempeltesttilfellet er én optimal sekvens $(2, 4)$, $(1, 4)$, $(1, 3)$, $(1, 4)$, $(2, 4)$. Dens antall operasjoner per avstand er $(0, 3, 2)$.