Little Cyan Fish er með umröðun $p_1, p_2, \ldots, p_n$ af heiltölunum frá $1$ til $n$, og eins og titill dæmisins gefur til kynna vill hann raða henni í hækkandi röð. Að þessu sinni er aðgerðin sem hann getur framkvæmt eftirfarandi.

• Í einni aðgerð má Little Cyan Fish velja tvær heiltölur $i$ og $j$ þannig að $1 \le i < j \le n$ og víxla $p_i$ og $p_j$.

En komdu nú, allir vita hvernig á að raða umröðun með einföldum víxlunum, svo augljóslega er það ekki það sem verkefnið biður þig um að gera. Í staðinn skilgreinir Little Cyan Fish fjarlægð aðgerðar sem $j - i$. Fyrir runu aðgerða sem raðar umröðuninni, látum $a_d$ tákna fjölda aðgerða með fjarlægð $d$, fyrir hvert $1 \le d < n$.

Meðal allra endanlegra runa aðgerða sem raða umröðuninni vill Little Cyan Fish að þú finnir þá runu $(a_1, a_2, \ldots, a_{n-1})$ sem er minnst í stafrófsröð (lexicographically smallest), og smíðir runu með í mesta lagi $5n$ aðgerðum sem nær því.

Inntak

Það eru mörg prófunartilvik. Fyrsta línan í inntakinu inniheldur eina heiltölu $T$ ($1 \le T \le 10^6$), sem gefur til kynna fjölda prófunartilvika.

Fyrir hvert prófunartilvik inniheldur fyrsta línan eina heiltölu $n$ ($2 \le n \le 10^6$), sem gefur til kynna lengd umröðunarinnar. Önnur línan inniheldur $n$ heiltölur $p_1, p_2, \ldots, p_n$ ($1 \le p_i \le n$), sem gefa til kynna umröðunina. Það er tryggt að $p$ sé umröðun af lengd $n$.

Það er tryggt að summa $n$ yfir öll prófunartilvik fari ekki yfir $10^6$.

Úttak

Fyrir hvert prófunartilvik skal skrifa út svarið á eftirfarandi sniði.

Fyrsta línan fyrir hvert prófunartilvik ætti að innihalda $n - 1$ heiltölur $a_1, a_2, \ldots, a_{n-1}$, minnstu rununa í stafrófsröð.

Önnur línan ætti að innihalda eina heiltölu $k$ ($0 \le k \le 5n$), fjölda aðgerða í rununni þinni.

Hver af næstu $k$ línum ætti að innihalda tvær heiltölur $i$ og $j$ ($1 \le i < j \le n$), vísana sem valdir voru í samsvarandi aðgerð. Aðgerðirnar, framkvæmdar í gefinni röð, verða að raða inntaksumröðuninni, og fyrir hvert $1 \le d < n$ verða nákvæmlega $a_d$ af aðgerðunum að hafa fjarlægð $d$.

Sýna má fram á að ákjósanleg runa með í mesta lagi $5n$ aðgerðum sé alltaf til. Ef það eru margar gildar runur aðgerða máttu skrifa út hvaða sem er af þeim.

Dæmi

Inntak 1

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

Úttak 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

Athugasemd

Í fyrsta sýnidæminu víxlar Little Cyan Fish sætum $1$ og $3$. Þetta raðar umröðuninni með einni aðgerð af fjarlægð $2$.

Í öðru sýnidæminu er ein ákjósanleg runa $(1, 4)$, $(2, 4)$, $(1, 4)$. Fjarlægðirnar eru $3$, $2$ og $3$, þannig að runan sem fæst er $(0, 1, 2)$.

Í þriðja sýnidæminu er ein ákjósanleg runa $(2, 4)$, $(1, 4)$, $(1, 3)$, $(1, 4)$, $(2, 4)$. Fjöldi aðgerða eftir fjarlægðum er $(0, 3, 2)$.