W roku 2077 układanie zadań staje się proste. Roboty generują zadanie, ustawiając pewne losowe operacje, a następnie same je rozwiązują. Autor zadania musi jedynie sprawdzić, czy zadanie jest poprawne, czy nie.

Oto zadanie z roku 2077:

Dana jest permutacja $p_1, p_2, \dots, p_n$, przy czym gwarantuje się, że $n$ jest parzyste. Chcesz posortować tę permutację, używając wyłącznie jednego rodzaju operacji:

• FakeSort(l,r): Musisz zagwarantować, że $r - l + 1$ jest parzyste. Niech $k = r - l + 1$, wówczas $k/2$ największych elementów oraz $k/2$ najmniejszych elementów w spójnym podciągu $p_l, p_{l+1}, \dots, p_r$ zostanie posortowanych niezależnie od siebie. Dokładniej, niech $L_1, L_2, \dots, L_{k/2}$ będą indeksami $k/2$ największych liczb, a $S_1, S_2, \dots, S_{k/2}$ będą indeksami $k/2$ najmniejszych liczb. Najpierw sortujemy liczby na indeksach $L_1 \sim L_{k/2}$, a następnie sortujemy liczby na indeksach $S_1 \sim S_{k/2}$.

Oto konkretny przykład; załóżmy, że permutacja to $p = \{2, 5, 7, 1, 8, 6, 4, 3\}$. Jeśli wywołamy FakeSort(2,7):

• $k = r - l + 1 = 6$. Spójny podciąg $p_l, p_{l+1}, \dots, p_r$ to $\{5, 7, 1, 8, 6, 4\}$; posortujemy niezależnie $3$ największe liczby oraz $3$ najmniejsze liczby tego ciągu.
• $p = \{2, 5, \mathbf{7}, 1, \mathbf{8}, \mathbf{6}, 4, 3\}$; $3$ największe liczby są pogrubione. Po posortowaniu stają się one $p = \{2, 5, \mathbf{6}, 1, \mathbf{7}, \mathbf{8}, 4, 3\}$.
• $p = \{2, \mathbf{5}, 6, \mathbf{1}, 7, 8, \mathbf{4}, 3\}$; $3$ najmniejsze liczby są pogrubione. Po posortowaniu stają się one $p = \{2, \mathbf{1}, 6, \mathbf{4}, 7, 8, \mathbf{5}, 3\}$.

Zatem $p = \{2, 5, 7, 1, 8, 6, 4, 3\}$ po wykonaniu FakeSort(2,7) staje się $\{2, 1, 6, 4, 7, 8, 5, 3\}$.

Użyj co najwyżej $114$ operacji, aby posortować permutację, lub stwierdź, że jest to niemożliwe. Można udowodnić, że jeśli permutację da się posortować za pomocą tej operacji, to istnieje sposób używający co najwyżej $114$ operacji.

Wejście

Wejście zawiera wiele przypadków testowych. Pierwszy wiersz wejścia zawiera liczbę całkowitą $T$ ($1 \le T \le 10^3$), oznaczającą liczbę przypadków testowych.

Dla każdego przypadku testowego pierwszy wiersz zawiera parzystą liczbę całkowitą $n$ ($4 \le n \le 10^5$), oznaczającą długość permutacji.

Drugi wiersz zawiera $n$ liczb całkowitych $p_1, p_2, \dots, p_n$ ($1 \le p_i \le n$), oznaczających permutację, którą musisz posortować. Gwarantuje się, że $p$ jest permutacją.

Gwarantuje się, że suma wartości $n$ po wszystkich przypadkach testowych nie przekracza $2 \times 10^5$.

Wyjście

Dla każdego przypadku testowego, jeśli posortowanie permutacji jest niemożliwe, wypisz $-1$.

W przeciwnym razie wypisz liczbę całkowitą $k$ ($0 \le k \le 114$), oznaczającą liczbę użytych operacji.

W kolejnych $k$ wierszach wypisz w każdym wierszu $l, r$ ($1 \le l \le r \le n$, $r - l + 1$ jest parzyste), co oznacza wykonanie FakeSort(l,r).

Przykłady

Przykładowe wejście 1

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

Przykładowe wyjście 1

1
1 4
-1
2
4 7
1 6