Nell'anno 2077 preparare problemi diventa semplice. I robot generano un problema impostando alcune operazioni casuali e poi lo risolvono. Chi prepara il problema deve solo controllare se il problema sia corretto oppure no.

Ecco un problema proveniente dal 2077:

Data una permutazione $p_1, p_2, \dots, p_n$, è garantito che $n$ è pari. Desideri ordinare la permutazione usando un solo tipo di operazione:

• FakeSort(l,r): Devi garantire che $r - l + 1$ sia pari. Sia $k = r - l + 1$; allora i $k/2$ elementi più grandi e i $k/2$ elementi più piccoli nella sottosequenza contigua $p_l, p_{l+1}, \dots, p_r$ verranno ordinati indipendentemente. Cioè, siano $L_1, L_2, \dots, L_{k/2}$ gli indici dei $k/2$ numeri più grandi, e $S_1, S_2, \dots, S_{k/2}$ gli indici dei $k/2$ numeri più piccoli. Prima ordiniamo i numeri sugli indici $L_1 \sim L_{k/2}$, poi ordiniamo i numeri sugli indici $S_1 \sim S_{k/2}$.

Ecco un esempio concreto; supponiamo che la permutazione sia $p = \{2, 5, 7, 1, 8, 6, 4, 3\}$. Se chiamiamo FakeSort(2,7):

• $k = r - l + 1 = 6$. La sottosequenza contigua $p_l, p_{l+1}, \dots, p_r$ è $\{5, 7, 1, 8, 6, 4\}$; ordineremo i $3$ numeri più grandi e i $3$ numeri più piccoli di questa sequenza in modo indipendente.
• $p = \{2, 5, \mathbf{7}, 1, \mathbf{8}, \mathbf{6}, 4, 3\}$; i $3$ numeri più grandi sono in grassetto. Dopo l'ordinamento diventano $p = \{2, 5, \mathbf{6}, 1, \mathbf{7}, \mathbf{8}, 4, 3\}$.
• $p = \{2, \mathbf{5}, 6, \mathbf{1}, 7, 8, \mathbf{4}, 3\}$; i $3$ numeri più piccoli sono in grassetto. Dopo l'ordinamento diventano $p = \{2, \mathbf{1}, 6, \mathbf{4}, 7, 8, \mathbf{5}, 3\}$.

Quindi $p = \{2, 5, 7, 1, 8, 6, 4, 3\}$ dopo FakeSort(2,7) diventa $\{2, 1, 6, 4, 7, 8, 5, 3\}$.

Usa non più di $114$ operazioni per ordinare la permutazione oppure determina che è impossibile. Si può dimostrare che, se una permutazione può essere ordinata con questa operazione, esiste un modo per farlo usando non più di $114$ operazioni.

Input

L'input contiene più casi di test. La prima riga dell'input contiene un intero $T$ ($1 \le T \le 10^3$), il numero di casi di test.

Per ciascun caso di test, la prima riga contiene un intero pari $n$ ($4 \le n \le 10^5$), la lunghezza della permutazione.

La seconda riga contiene $n$ interi $p_1, p_2, \dots, p_n$ ($1 \le p_i \le n$), la permutazione che devi ordinare. È garantito che $p$ sia una permutazione.

È garantito che la somma di $n$ su tutti i casi di test non superi $2 \times 10^5$.

Output

Per ciascun caso di test, se è impossibile ordinare la permutazione, stampa $-1$.

Altrimenti, stampa un intero $k$ ($0 \le k \le 114$), che indica il numero di operazioni utilizzate.

Nelle successive $k$ righe, stampa $l, r$ ($1 \le l \le r \le n$, $r - l + 1$ è pari) in ciascuna riga, per indicare l'esecuzione di FakeSort(l,r).

Esempi

Input di esempio 1

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

Output di esempio 1

1
1 4
-1
2
4 7
1 6