Im Jahr 2077 wird das Erstellen von Aufgaben einfach. Roboter generieren eine Aufgabe, indem sie einige zufällige Operationen festlegen, und lösen sie anschließend selbst. Ein Aufgabensteller muss nur noch prüfen, ob die Aufgabe korrekt ist oder nicht.

Hier ist eine Aufgabe aus dem Jahr 2077:

Gegeben ist eine Permutation $p_1, p_2, \dots, p_n$, wobei garantiert ist, dass $n$ gerade ist. Du möchtest die Permutation sortieren und dabei nur einen einzigen Operationstyp verwenden:

• FakeSort(l,r): Du musst sicherstellen, dass $r - l + 1$ gerade ist. Sei $k = r - l + 1$, dann werden die größten $k/2$ Elemente und die kleinsten $k/2$ Elemente in der zusammenhängenden Teilfolge $p_l, p_{l+1}, \dots, p_r$ unabhängig voneinander sortiert. Das heißt, seien $L_1, L_2, \dots, L_{k/2}$ die Indizes der größten $k/2$ Zahlen und $S_1, S_2, \dots, S_{k/2}$ die Indizes der kleinsten $k/2$ Zahlen. Wir sortieren zuerst die Zahlen an den Indizes $L_1 \sim L_{k/2}$ und anschließend die Zahlen an den Indizes $S_1 \sim S_{k/2}$.

Hier ist ein konkretes Beispiel; angenommen, die Permutation lautet $p = \{2, 5, 7, 1, 8, 6, 4, 3\}$. Wenn wir FakeSort(2,7) aufrufen:

• $k = r - l + 1 = 6$. Die zusammenhängende Teilfolge $p_l, p_{l+1}, \dots, p_r$ ist $\{5, 7, 1, 8, 6, 4\}$; wir sortieren die größten $3$ Zahlen und die kleinsten $3$ Zahlen dieser Folge unabhängig voneinander.
• $p = \{2, 5, \mathbf{7}, 1, \mathbf{8}, \mathbf{6}, 4, 3\}$; die größten $3$ Zahlen sind fett gedruckt. Nach dem Sortieren wird daraus $p = \{2, 5, \mathbf{6}, 1, \mathbf{7}, \mathbf{8}, 4, 3\}$.
• $p = \{2, \mathbf{5}, 6, \mathbf{1}, 7, 8, \mathbf{4}, 3\}$; die kleinsten $3$ Zahlen sind fett gedruckt. Nach dem Sortieren wird daraus $p = \{2, \mathbf{1}, 6, \mathbf{4}, 7, 8, \mathbf{5}, 3\}$.

Also wird $p = \{2, 5, 7, 1, 8, 6, 4, 3\}$ nach FakeSort(2,7) zu $\{2, 1, 6, 4, 7, 8, 5, 3\}$.

Bitte verwende höchstens $114$ Operationen, um die Permutation zu sortieren, oder stelle fest, dass dies unmöglich ist. Es lässt sich beweisen, dass es, falls eine Permutation mit dieser Operation sortiert werden kann, immer eine Möglichkeit gibt, die höchstens $114$ Operationen benötigt.

Eingabe

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

Für jeden Testfall enthält die erste Zeile eine gerade ganze Zahl $n$ ($4 \le n \le 10^5$), die Länge der Permutation.

Die zweite Zeile enthält $n$ ganze Zahlen $p_1, p_2, \dots, p_n$ ($1 \le p_i \le n$), die Permutation, die du sortieren musst. Es wird garantiert, dass $p$ eine Permutation ist.

Es wird garantiert, dass die Summe von $n$ über alle Testfälle hinweg $2 \times 10^5$ nicht überschreitet.

Ausgabe

Für jeden Testfall gib $-1$ aus, falls es unmöglich ist, die Permutation zu sortieren.

Andernfalls gib eine ganze Zahl $k$ ($0 \le k \le 114$) aus, die die Anzahl der verwendeten Operationen angibt.

Gib in den folgenden $k$ Zeilen jeweils $l, r$ ($1 \le l \le r \le n$, $r - l + 1$ ist gerade) aus, was die Ausführung von FakeSort(l,r) bedeutet.

Beispiele

Beispieleingabe 1

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

Beispielausgabe 1

1
1 4
-1
2
4 7
1 6