Little Cyan Fish hat eine Permutation $p_1, p_2, \ldots, p_n$ der ganzen Zahlen von $1$ bis $n$, und wie der Titel der Aufgabe vermuten lässt, möchte er sie in aufsteigender Reihenfolge sortieren. Diesmal lautet die Operation, die er ausführen kann, wie folgt.

• In einer Operation darf Little Cyan Fish zwei ganze Zahlen $i$ und $j$ mit $1 \le i < j \le n$ wählen und $p_i$ sowie $p_j$ vertauschen.

Aber mal ehrlich: Jeder weiß, wie man eine Permutation mit einfachen Vertauschungen sortiert, also ist das offensichtlich nicht alles, was diese Aufgabe von dir verlangt. Stattdessen definiert Little Cyan Fish die Distanz einer Operation als $j - i$. Für eine Folge von Operationen, die die Permutation sortiert, bezeichne $a_d$ die Anzahl der Operationen mit Distanz $d$ für jedes $1 \le d < n$.

Unter allen endlichen Folgen von Operationen, die die Permutation sortieren, möchte Little Cyan Fish, dass du die lexikographisch kleinste Folge $(a_1, a_2, \ldots, a_{n-1})$ findest und eine Folge von höchstens $5n$ Operationen konstruierst, die diese erreicht.

Eingabe

Es gibt mehrere Testfälle. Die erste Zeile der Eingabe enthält eine einzelne ganze Zahl $T$ ($1 \le T \le 10^6$), die die Anzahl der Testfälle angibt.

Für jeden Testfall enthält die erste Zeile eine einzelne ganze Zahl $n$ ($2 \le n \le 10^6$), die die Länge der Permutation angibt. Die zweite Zeile enthält $n$ ganze Zahlen $p_1, p_2, \ldots, p_n$ ($1 \le p_i \le n$), die die Permutation angeben. Es wird garantiert, dass $p$ eine Permutation der Länge $n$ ist.

Es wird garantiert, dass die Summe von $n$ über alle Testfälle $10^6$ nicht überschreitet.

Ausgabe

Gib für jeden Testfall die Antwort im folgenden Format aus.

Die erste Zeile für jeden Testfall soll $n - 1$ ganze Zahlen $a_1, a_2, \ldots, a_{n-1}$ enthalten, die lexikographisch kleinste Folge.

Die zweite Zeile soll eine einzelne ganze Zahl $k$ ($0 \le k \le 5n$) enthalten, die Anzahl der Operationen in deiner Folge.

Jede der folgenden $k$ Zeilen soll zwei ganze Zahlen $i$ und $j$ ($1 \le i < j \le n$) enthalten, die in der entsprechenden Operation gewählten Indizes. Die Operationen müssen, wenn sie in der angegebenen Reihenfolge ausgeführt werden, die Eingabepermutation sortieren, und für jedes $1 \le d < n$ müssen genau $a_d$ der Operationen die Distanz $d$ haben.

Es lässt sich zeigen, dass stets eine optimale Folge von höchstens $5n$ Operationen existiert. Falls es mehrere gültige Folgen von Operationen gibt, kannst du eine beliebige davon ausgeben.

Beispiele

Eingabe 1

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

Ausgabe 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

Hinweis

Im ersten Beispieltestfall vertauscht Little Cyan Fish die Positionen $1$ und $3$. Dadurch wird die Permutation mit einer einzigen Operation der Distanz $2$ sortiert.

Im zweiten Beispieltestfall ist eine optimale Folge $(1, 4)$, $(2, 4)$, $(1, 4)$. Die Distanzen sind $3$, $2$ und $3$, sodass die resultierende Folge $(0, 1, 2)$ lautet.

Im dritten Beispieltestfall ist eine optimale Folge $(2, 4)$, $(1, 4)$, $(1, 3)$, $(1, 4)$, $(2, 4)$. Die Häufigkeiten der Distanzen betragen $(0, 3, 2)$.