Vuonna 2077 tehtävien laatimisesta tulee yksinkertaista. Robotit luovat tehtävän asettamalla muutamia satunnaisia operaatioita ja ratkaisevat sen sitten itse. Tehtävänlaatijan tarvitsee vain tarkistaa, onko tehtävä oikein vai ei.

Tässä on tehtävä vuodelta 2077:

Annettuna on permutaatio $p_1, p_2, \dots, p_n$, ja on taattua, että $n$ on parillinen. Haluat järjestää permutaation käyttämällä vain yhdenlaista operaatiota:

• FakeSort(l,r): Sinun on varmistettava, että $r - l + 1$ on parillinen. Olkoon $k = r - l + 1$, jolloin yhtenäisen alijonon $p_l, p_{l+1}, \dots, p_r$ suurimmat $k/2$ alkiota ja pienimmät $k/2$ alkiota järjestetään toisistaan riippumatta. Toisin sanoen olkoot $L_1, L_2, \dots, L_{k/2}$ suurimpien $k/2$ luvun indeksit ja $S_1, S_2, \dots, S_{k/2}$ pienimpien $k/2$ luvun indeksit. Järjestämme ensin indekseissä $L_1 \sim L_{k/2}$ olevat luvut ja sen jälkeen indekseissä $S_1 \sim S_{k/2}$ olevat luvut.

Tässä on konkreettinen esimerkki; oletetaan, että permutaatio on $p = \{2, 5, 7, 1, 8, 6, 4, 3\}$. Jos kutsumme FakeSort(2,7):

• $k = r - l + 1 = 6$. Yhtenäinen alijono $p_l, p_{l+1}, \dots, p_r$ on $\{5, 7, 1, 8, 6, 4\}$; järjestämme tämän jonon suurimmat $3$ lukua ja pienimmät $3$ lukua toisistaan riippumatta.
• $p = \{2, 5, \mathbf{7}, 1, \mathbf{8}, \mathbf{6}, 4, 3\}$; suurimmat $3$ lukua on lihavoitu. Järjestämisen jälkeen niistä tulee $p = \{2, 5, \mathbf{6}, 1, \mathbf{7}, \mathbf{8}, 4, 3\}$.
• $p = \{2, \mathbf{5}, 6, \mathbf{1}, 7, 8, \mathbf{4}, 3\}$; pienimmät $3$ lukua on lihavoitu. Järjestämisen jälkeen niistä tulee $p = \{2, \mathbf{1}, 6, \mathbf{4}, 7, 8, \mathbf{5}, 3\}$.

Siispä $p = \{2, 5, 7, 1, 8, 6, 4, 3\}$ muuttuu operaation FakeSort(2,7) jälkeen muotoon $\{2, 1, 6, 4, 7, 8, 5, 3\}$.

Käytä enintään $114$ operaatiota permutaation järjestämiseen tai päätä, että se on mahdotonta. Voidaan todistaa, että jos permutaatio voidaan järjestää tällä operaatiolla, on olemassa tapa käyttää enintään $114$ operaatiota.

Syöte

Syöte sisältää useita testitapauksia. Syötteen ensimmäinen rivi sisältää kokonaisluvun $T$ ($1 \le T \le 10^3$), testitapausten lukumäärän.

Kunkin testitapauksen ensimmäinen rivi sisältää parillisen kokonaisluvun $n$ ($4 \le n \le 10^5$), permutaation pituuden.

Toinen rivi sisältää $n$ kokonaislukua $p_1, p_2, \dots, p_n$ ($1 \le p_i \le n$), järjestettävän permutaation. On taattua, että $p$ on permutaatio.

On taattua, että lukujen $n$ summa yli kaikkien testitapausten on enintään $2 \times 10^5$.

Tuloste

Jokaiselle testitapaukselle, jos permutaation järjestäminen on mahdotonta, tulosta $-1$.

Muussa tapauksessa tulosta kokonaisluku $k$ ($0 \le k \le 114$), joka ilmaisee käytettyjen operaatioiden määrän.

Seuraavilla $k$ rivillä tulosta kullekin riville $l, r$ ($1 \le l \le r \le n$, $r - l + 1$ on parillinen), mikä tarkoittaa operaation FakeSort(l,r) suorittamista.

Esimerkit

Esimerkkisyöte 1

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

Esimerkkituloste 1

1
1 4
-1
2
4 7
1 6