Little Cyan Fish ma permutację $p_1, p_2, \ldots, p_n$ liczb całkowitych od $1$ do $n$ i, jak sugeruje tytuł zadania, chce posortować ją rosnąco. Tym razem operacja, którą może wykonać, wygląda następująco.

• W jednej operacji Little Cyan Fish może wybrać dwie liczby całkowite $i$ oraz $j$ takie, że $1 \le i < j \le n$, i zamienić miejscami $p_i$ oraz $p_j$.

Ale dajmy spokój, każdy wie, jak posortować permutację za pomocą prostych zamian, więc oczywiście nie o to chodzi w tym zadaniu. Zamiast tego Little Cyan Fish definiuje odległość operacji jako $j - i$. Dla ciągu operacji sortującego permutację niech $a_d$ oznacza liczbę operacji o odległości $d$, dla każdego $1 \le d < n$.

Spośród wszystkich skończonych ciągów operacji, które sortują permutację, Little Cyan Fish chce, abyś znalazł najmniejszy leksykograficznie ciąg $(a_1, a_2, \ldots, a_{n-1})$ oraz skonstruował ciąg co najwyżej $5n$ operacji, który go realizuje.

Wejście

Wejście składa się z wielu przypadków testowych. Pierwszy wiersz wejścia zawiera jedną liczbę całkowitą $T$ ($1 \le T \le 10^6$), oznaczającą liczbę przypadków testowych.

Dla każdego przypadku testowego pierwszy wiersz zawiera jedną liczbę całkowitą $n$ ($2 \le n \le 10^6$), oznaczającą długość permutacji. Drugi wiersz zawiera $n$ liczb całkowitych $p_1, p_2, \ldots, p_n$ ($1 \le p_i \le n$), opisujących permutację. Gwarantowane jest, że $p$ jest permutacją o długości $n$.

Gwarantowane jest, że suma wartości $n$ po wszystkich przypadkach testowych nie przekracza $10^6$.

Wyjście

Dla każdego przypadku testowego wypisz odpowiedź w następującym formacie.

Pierwszy wiersz dla każdego przypadku testowego powinien zawierać $n - 1$ liczb całkowitych $a_1, a_2, \ldots, a_{n-1}$, oznaczających najmniejszy leksykograficznie ciąg.

Drugi wiersz powinien zawierać jedną liczbę całkowitą $k$ ($0 \le k \le 5n$), oznaczającą liczbę operacji w Twoim ciągu.

Każdy z kolejnych $k$ wierszy powinien zawierać dwie liczby całkowite $i$ oraz $j$ ($1 \le i < j \le n$), oznaczające indeksy wybrane w odpowiedniej operacji. Operacje wykonane w podanej kolejności muszą posortować wejściową permutację, a ponadto dla każdego $1 \le d < n$ dokładnie $a_d$ operacji musi mieć odległość $d$.

Można wykazać, że optymalny ciąg składający się z co najwyżej $5n$ operacji zawsze istnieje. Jeśli istnieje wiele poprawnych ciągów operacji, możesz wypisać dowolny z nich.

Przykład

Wejście 1

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

Wyjście 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

Uwagi

W pierwszym przykładowym przypadku testowym Little Cyan Fish zamienia miejscami pozycje $1$ oraz $3$. Sortuje to permutację za pomocą jednej operacji o odległości $2$.

W drugim przykładowym przypadku testowym jednym z optymalnych ciągów jest $(1, 4)$, $(2, 4)$, $(1, 4)$. Odległości wynoszą $3$, $2$ oraz $3$, więc wynikowy ciąg to $(0, 1, 2)$.

W trzecim przykładowym przypadku testowym jednym z optymalnych ciągów jest $(2, 4)$, $(1, 4)$, $(1, 3)$, $(1, 4)$, $(2, 4)$. Liczby operacji dla poszczególnych odległości to $(0, 3, 2)$.