En l'an 2077, la création de problèmes devient simple. Des robots génèrent un problème en définissant quelques opérations aléatoires, puis le résolvent. Un auteur de problème doit seulement vérifier si le problème est correct ou non.

Voici un problème venu de 2077 :

On vous donne une permutation $p_1, p_2, \dots, p_n$, en garantissant que $n$ est pair. Vous souhaitez trier cette permutation en utilisant un seul type d'opération :

• FakeSort(l,r) : Vous devez garantir que $r - l + 1$ est pair. Soit $k = r - l + 1$ ; alors les $k/2$ plus grands éléments et les $k/2$ plus petits éléments de la sous-séquence contiguë $p_l, p_{l+1}, \dots, p_r$ seront triés indépendamment. Autrement dit, soient $L_1, L_2, \dots, L_{k/2}$ les indices des $k/2$ plus grands nombres, et $S_1, S_2, \dots, S_{k/2}$ les indices des $k/2$ plus petits nombres. Nous trions d'abord les nombres aux indices $L_1 \sim L_{k/2}$, puis nous trions les nombres aux indices $S_1 \sim S_{k/2}$.

Voici un exemple concret ; supposons que la permutation soit $p = \{2, 5, 7, 1, 8, 6, 4, 3\}$. Si nous appelons FakeSort(2,7) :

• $k = r - l + 1 = 6$. La sous-séquence contiguë $p_l, p_{l+1}, \dots, p_r$ est $\{5, 7, 1, 8, 6, 4\}$ ; nous allons trier les $3$ plus grands nombres et les $3$ plus petits nombres de cette séquence indépendamment.
• $p = \{2, 5, \mathbf{7}, 1, \mathbf{8}, \mathbf{6}, 4, 3\}$ ; les $3$ plus grands nombres sont en gras. Après le tri, cela devient $p = \{2, 5, \mathbf{6}, 1, \mathbf{7}, \mathbf{8}, 4, 3\}$.
• $p = \{2, \mathbf{5}, 6, \mathbf{1}, 7, 8, \mathbf{4}, 3\}$ ; les $3$ plus petits nombres sont en gras. Après le tri, cela devient $p = \{2, \mathbf{1}, 6, \mathbf{4}, 7, 8, \mathbf{5}, 3\}$.

Ainsi, $p = \{2, 5, 7, 1, 8, 6, 4, 3\}$ après FakeSort(2,7) devient $\{2, 1, 6, 4, 7, 8, 5, 3\}$.

Veuillez utiliser au plus $114$ opérations pour trier la permutation ou déterminer que c'est impossible. On peut prouver que si une permutation peut être triée avec cette opération, il existe une méthode utilisant au plus $114$ opérations.

Entrée

L'entrée contient plusieurs cas de test. La première ligne de l'entrée contient un entier $T$ ($1 \le T \le 10^3$), le nombre de cas de test.

Pour chaque cas de test, la première ligne contient un entier pair $n$ ($4 \le n \le 10^5$), la longueur de la permutation.

La deuxième ligne contient $n$ entiers $p_1, p_2, \dots, p_n$ ($1 \le p_i \le n$), la permutation que vous devez trier. Il est garanti que $p$ est une permutation.

Il est garanti que la somme de $n$ sur l'ensemble des cas de test ne dépasse pas $2 \times 10^5$.

Sortie

Pour chaque cas de test, s'il est impossible de trier la permutation, affichez $-1$.

Sinon, affichez un entier $k$ ($0 \le k \le 114$), indiquant le nombre d'opérations utilisées.

Sur les $k$ lignes suivantes, affichez $l, r$ ($1 \le l \le r \le n$, $r - l + 1$ est pair) sur chaque ligne, indiquant l'exécution de FakeSort(l,r).

Exemples

Exemple d'entrée 1

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

Exemple de sortie 1

1
1 4
-1
2
4 7
1 6