Little Cyan Fishillä on permutaatio $p_1, p_2, \ldots, p_n$ kokonaisluvuista väliltä $1$ – $n$, ja kuten tehtävän otsikko vihjaa, hän haluaa järjestää sen nousevaan järjestykseen. Tällä kertaa operaatio, jonka hän voi suorittaa, on seuraavanlainen.

• Yhdessä operaatiossa Little Cyan Fish voi valita kaksi kokonaislukua $i$ ja $j$ siten, että $1 \le i < j \le n$, ja vaihtaa lukujen $p_i$ ja $p_j$ paikat keskenään.

Mutta hei, jokainenhan osaa järjestää permutaation yksinkertaisilla vaihdoilla, joten tehtävässä ei selvästikään pyydetä tekemään vain sitä. Sen sijaan Little Cyan Fish määrittelee operaation etäisyydeksi erotuksen $j - i$. Permutaation järjestävälle operaatioiden jonolle merkitään luvulla $a_d$ niiden operaatioiden lukumäärää, joiden etäisyys on $d$, jokaisella $1 \le d < n$.

Kaikkien permutaation järjestävien äärellisten operaatiojonojen joukosta Little Cyan Fish haluaa sinun etsivän leksikografisesti pienimmän jonon $(a_1, a_2, \ldots, a_{n-1})$ ja muodostavan korkeintaan $5n$ operaation jonon, jolla se saavutetaan.

Syöte

Syötteessä on useita testitapauksia. Syötteen ensimmäinen rivi sisältää yhden kokonaisluvun $T$ ($1 \le T \le 10^6$), joka ilmaisee testitapausten lukumäärän.

Jokaisessa testitapauksessa ensimmäinen rivi sisältää yhden kokonaisluvun $n$ ($2 \le n \le 10^6$), joka ilmaisee permutaation pituuden. Toinen rivi sisältää $n$ kokonaislukua $p_1, p_2, \ldots, p_n$ ($1 \le p_i \le n$), jotka ilmaisevat permutaation. On taattu, että $p$ on pituuden $n$ permutaatio.

On taattu, että lukujen $n$ summa yli kaikkien testitapausten ei ylitä arvoa $10^6$.

Tuloste

Tulosta jokaiselle testitapaukselle vastaus seuraavassa muodossa.

Jokaisen testitapauksen ensimmäisen rivin tulee sisältää $n - 1$ kokonaislukua $a_1, a_2, \ldots, a_{n-1}$, eli leksikografisesti pienin jono.

Toisen rivin tulee sisältää yksi kokonaisluku $k$ ($0 \le k \le 5n$), eli operaatioiden lukumäärä muodostamassasi jonossa.

Jokaisen seuraavista $k$ rivistä tulee sisältää kaksi kokonaislukua $i$ ja $j$ ($1 \le i < j \le n$), jotka ovat vastaavassa operaatiossa valitut indeksit. Annetussa järjestyksessä suoritettujen operaatioiden täytyy järjestää syötteen permutaatio, ja jokaisella $1 \le d < n$ täsmälleen $a_d$ operaation etäisyyden täytyy olla $d$.

Voidaan osoittaa, että korkeintaan $5n$ operaation optimaalinen jono on aina olemassa. Jos kelvollisia operaatiojonoja on useita, voit tulostaa niistä minkä tahansa.

Esimerkit

Syöte 1

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

Tuloste 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

Huomautus

Ensimmäisessä esimerkkitestitapauksessa Little Cyan Fish vaihtaa paikat $1$ ja $3$ keskenään. Tämä järjestää permutaation yhdellä operaatiolla, jonka etäisyys on $2$.

Toisessa esimerkkitestitapauksessa eräs optimaalinen jono on $(1, 4)$, $(2, 4)$, $(1, 4)$. Etäisyydet ovat $3$, $2$ ja $3$, joten tuloksena saatava jono on $(0, 1, 2)$.

Kolmannessa esimerkkitestitapauksessa eräs optimaalinen jono on $(2, 4)$, $(1, 4)$, $(1, 3)$, $(1, 4)$, $(2, 4)$. Sen etäisyyskohtaiset lukumäärät ovat $(0, 3, 2)$.