Little Cyan Fish har en permutation $p_1, p_2, \ldots, p_n$ av heltalen från $1$ till $n$, och som titeln på problemet antyder vill han sortera den i stigande ordning. Den här gången är operationen han kan utföra följande.

• I en operation får Little Cyan Fish välja två heltal $i$ och $j$ sådana att $1 \le i < j \le n$ och byta plats på $p_i$ och $p_j$.

Men kom igen, alla vet hur man sorterar en permutation med enkla platsbyten, så uppenbarligen är det inte detta som uppgiften ber dig att göra. Istället definierar Little Cyan Fish avståndet för en operation som $j - i$. För en sekvens av operationer som sorterar permutationen, låt $a_d$ beteckna antalet operationer med avstånd $d$, för varje $1 \le d < n$.

Bland alla ändliga sekvenser av operationer som sorterar permutationen vill Little Cyan Fish att du hittar den lexikografiskt minsta sekvensen $(a_1, a_2, \ldots, a_{n-1})$, och konstruerar en sekvens av högst $5n$ operationer som uppnår den.

Indata

Det finns flera testfall. Den första raden i indatan innehåller ett enda heltal $T$ ($1 \le T \le 10^6$), som anger antalet testfall.

För varje testfall innehåller den första raden ett enda heltal $n$ ($2 \le n \le 10^6$), som anger permutationens längd. Den andra raden innehåller $n$ heltal $p_1, p_2, \ldots, p_n$ ($1 \le p_i \le n$), som anger permutationen. Det garanteras att $p$ är en permutation av längd $n$.

Det garanteras att summan av $n$ över alla testfall inte överstiger $10^6$.

Utdata

För varje testfall, skriv ut svaret i följande format.

Den första raden för varje testfall ska innehålla $n - 1$ heltal $a_1, a_2, \ldots, a_{n-1}$, den lexikografiskt minsta sekvensen.

Den andra raden ska innehålla ett enda heltal $k$ ($0 \le k \le 5n$), antalet operationer i din sekvens.

Var och en av de följande $k$ raderna ska innehålla två heltal $i$ och $j$ ($1 \le i < j \le n$), indexen som valts i motsvarande operation. Operationerna, utförda i den angivna ordningen, måste sortera indatapermutationen, och för varje $1 \le d < n$ måste exakt $a_d$ av operationerna ha avstånd $d$.

Det kan visas att en optimal sekvens med högst $5n$ operationer alltid existerar. Om det finns flera giltiga sekvenser av operationer kan du skriva ut vilken som helst av dem.

Exempel

Indata 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

Förklaring

I det första exempeltestfallet byter Little Cyan Fish plats på positionerna $1$ och $3$. Detta sorterar permutationen med hjälp av en operation med avstånd $2$.

I det andra exempeltestfallet är en optimal sekvens $(1, 4)$, $(2, 4)$, $(1, 4)$. Avstånden är $3$, $2$ och $3$, så den resulterande sekvensen blir $(0, 1, 2)$.

I det tredje exempeltestfallet är en optimal sekvens $(2, 4)$, $(1, 4)$, $(1, 3)$, $(1, 4)$, $(2, 4)$. Dess antal operationer per avstånd är $(0, 3, 2)$.