Little Cyan Fish dispose d'une permutation $p_1, p_2, \ldots, p_n$ des entiers de $1$ à $n$ et, comme le suggère le titre du problème, il souhaite la trier par ordre croissant. Cette fois-ci, l'opération qu'il peut effectuer est la suivante.

• En une opération, Little Cyan Fish peut choisir deux entiers $i$ et $j$ tels que $1 \le i < j \le n$ et échanger $p_i$ et $p_j$.

Mais voyons, tout le monde sait trier une permutation avec de simples échanges, ce n'est donc évidemment pas ce que l'on vous demande de faire. À la place, Little Cyan Fish définit la distance d'une opération comme étant $j - i$. Pour une séquence d'opérations qui trie la permutation, soit $a_d$ le nombre d'opérations de distance $d$, pour chaque $1 \le d < n$.

Parmi toutes les séquences finies d'opérations qui trient la permutation, Little Cyan Fish vous demande de trouver la séquence $(a_1, a_2, \ldots, a_{n-1})$ lexicographiquement minimale, et de construire une séquence d'au plus $5n$ opérations permettant de l'atteindre.

Entrée

Il y a plusieurs cas de test. La première ligne de l'entrée contient un seul entier $T$ ($1 \le T \le 10^6$), indiquant le nombre de cas de test.

Pour chaque cas de test, la première ligne contient un seul entier $n$ ($2 \le n \le 10^6$), indiquant la longueur de la permutation. La deuxième ligne contient $n$ entiers $p_1, p_2, \ldots, p_n$ ($1 \le p_i \le n$), indiquant la permutation. Il est garanti que $p$ est une permutation de longueur $n$.

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

Sortie

Pour chaque cas de test, affichez la réponse au format suivant.

La première ligne de chaque cas de test doit contenir $n - 1$ entiers $a_1, a_2, \ldots, a_{n-1}$, la séquence lexicographiquement minimale.

La deuxième ligne doit contenir un seul entier $k$ ($0 \le k \le 5n$), le nombre d'opérations dans votre séquence.

Chacune des $k$ lignes suivantes doit contenir deux entiers $i$ et $j$ ($1 \le i < j \le n$), les indices choisis lors de l'opération correspondante. Les opérations, effectuées dans l'ordre donné, doivent trier la permutation fournie en entrée, et pour chaque $1 \le d < n$, exactement $a_d$ opérations doivent avoir une distance égale à $d$.

On peut montrer qu'il existe toujours une séquence optimale d'au plus $5n$ opérations. S'il existe plusieurs séquences d'opérations valides, vous pouvez afficher n'importe laquelle d'entre elles.

Exemples

Entrée 1

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

Sortie 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

Remarque

Dans le premier cas de test de l'exemple, Little Cyan Fish échange les positions $1$ et $3$. Cela trie la permutation en utilisant une opération de distance $2$.

Dans le deuxième cas de test de l'exemple, une séquence optimale est $(1, 4)$, $(2, 4)$, $(1, 4)$. Les distances sont $3$, $2$ et $3$, de sorte que la séquence résultante est $(0, 1, 2)$.

Dans le troisième cas de test de l'exemple, une séquence optimale est $(2, 4)$, $(1, 4)$, $(1, 3)$, $(1, 4)$, $(2, 4)$. Ses nombres d'opérations par distance sont $(0, 3, 2)$.