I året 2077 blir det enkelt å lage oppgaver. Roboter genererer en oppgave ved å sette opp noen tilfeldige operasjoner og deretter løse den. En oppgaveforfatter trenger bare å sjekke om oppgaven er korrekt eller ikke.

Her er en oppgave fra 2077:

Gitt en permutasjon $p_1, p_2, \dots, p_n$, der det er garantert at $n$ er et partall. Du ønsker å sortere permutasjonen ved å bruke kun én type operasjon:

• FakeSort(l,r): Du må garantere at $r - l + 1$ er et partall. La $k = r - l + 1$, da vil de $k/2$ største elementene og de $k/2$ minste elementene i den sammenhengende delsekvensen $p_l, p_{l+1}, \dots, p_r$ bli sortert uavhengig av hverandre. Det vil si, la $L_1, L_2, \dots, L_{k/2}$ være indeksene til de $k/2$ største tallene, og $S_1, S_2, \dots, S_{k/2}$ være indeksene til de $k/2$ minste tallene. Vi sorterer først tallene på indeksene $L_1 \sim L_{k/2}$, og deretter sorterer vi tallene på indeksene $S_1 \sim S_{k/2}$.

Her er et konkret eksempel; anta at permutasjonen er $p = \{2, 5, 7, 1, 8, 6, 4, 3\}$. Hvis vi kaller FakeSort(2,7):

• $k = r - l + 1 = 6$. Den sammenhengende delsekvensen $p_l, p_{l+1}, \dots, p_r$ er $\{5, 7, 1, 8, 6, 4\}$; vi vil sortere de $3$ største tallene og de $3$ minste tallene i denne sekvensen uavhengig av hverandre.
• $p = \{2, 5, \mathbf{7}, 1, \mathbf{8}, \mathbf{6}, 4, 3\}$; de $3$ største tallene er i fet skrift. Etter sortering blir de til $p = \{2, 5, \mathbf{6}, 1, \mathbf{7}, \mathbf{8}, 4, 3\}$.
• $p = \{2, \mathbf{5}, 6, \mathbf{1}, 7, 8, \mathbf{4}, 3\}$; de $3$ minste tallene er i fet skrift. Etter sortering blir de til $p = \{2, \mathbf{1}, 6, \mathbf{4}, 7, 8, \mathbf{5}, 3\}$.

Så $p = \{2, 5, 7, 1, 8, 6, 4, 3\}$ blir etter FakeSort(2,7) til $\{2, 1, 6, 4, 7, 8, 5, 3\}$.

Vennligst bruk ikke mer enn $114$ operasjoner for å sortere permutasjonen, eller avgjør at det er umulig. Det kan bevises at hvis en permutasjon kan sorteres med denne operasjonen, finnes det en måte å bruke høyst $114$ operasjoner på.

Inndata

Inndataene inneholder flere testtilfeller. Den første linjen i inndataene inneholder et heltall $T$ ($1 \le T \le 10^3$), antall testtilfeller.

For hvert testtilfelle inneholder den første linjen et partall $n$ ($4 \le n \le 10^5$), lengden på permutasjonen.

Den andre linjen inneholder $n$ heltall $p_1, p_2, \dots, p_n$ ($1 \le p_i \le n$), permutasjonen du skal sortere. Det er garantert at $p$ er en permutasjon.

Det er garantert at summen av $n$ over alle testtilfeller ikke overstiger $2 \times 10^5$.

Utdata

For hvert testtilfelle, hvis det er umulig å sortere permutasjonen, skriv ut $-1$.

Ellers skriv ut et heltall $k$ ($0 \le k \le 114$), som angir antall operasjoner som brukes.

På de følgende $k$ linjene, skriv ut $l, r$ ($1 \le l \le r \le n$, $r - l + 1$ er et partall) på hver linje, som angir at FakeSort(l,r) utføres.

Eksempler

Eksempelinndata 1

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

Eksempelutdata 1

1
1 4
-1
2
4 7
1 6