Маленька Блакитна Рибка має перестановку $p_1, p_2, \ldots, p_n$ цілих чисел від $1$ до $n$ і, як випливає з назви задачі, хоче відсортувати її за зростанням. Цього разу операція, яку вона може виконувати, є такою.

• За одну операцію Маленька Блакитна Рибка може вибрати два цілі числа $i$ та $j$, такі що $1 \le i < j \le n$, і поміняти місцями $p_i$ та $p_j$.

Але, погодьтеся, кожен вміє сортувати перестановку простими обмінами, тож очевидно, що задача вимагає від вас не цього. Натомість Маленька Блакитна Рибка визначає відстань операції як $j - i$. Для послідовності операцій, що сортує перестановку, позначимо через $a_d$ кількість операцій з відстанню $d$ для кожного $1 \le d < n$.

Серед усіх скінченних послідовностей операцій, що сортують перестановку, Маленька Блакитна Рибка хоче, щоб ви знайшли лексикографічно найменшу послідовність $(a_1, a_2, \ldots, a_{n-1})$ і побудували послідовність із щонайбільше $5n$ операцій, яка її досягає.

Вхідні дані

Тест складається з кількох наборів вхідних даних. Перший рядок вхідних даних містить одне ціле число $T$ ($1 \le T \le 10^6$), що позначає кількість наборів вхідних даних.

Для кожного набору вхідних даних перший рядок містить одне ціле число $n$ ($2 \le n \le 10^6$), що позначає довжину перестановки. Другий рядок містить $n$ цілих чисел $p_1, p_2, \ldots, p_n$ ($1 \le p_i \le n$), що задають перестановку. Гарантується, що $p$ є перестановкою довжини $n$.

Гарантується, що сума $n$ за всіма наборами вхідних даних не перевищує $10^6$.

Вихідні дані

Для кожного набору вхідних даних виведіть відповідь у наведеному нижче форматі.

Перший рядок для кожного набору вхідних даних повинен містити $n - 1$ цілих чисел $a_1, a_2, \ldots, a_{n-1}$ — лексикографічно найменшу послідовність.

Другий рядок повинен містити одне ціле число $k$ ($0 \le k \le 5n$) — кількість операцій у вашій послідовності.

Кожен із наступних $k$ рядків повинен містити два цілі числа $i$ та $j$ ($1 \le i < j \le n$) — індекси, вибрані у відповідній операції. Операції, виконані в заданому порядку, повинні відсортувати вхідну перестановку, і для кожного $1 \le d < n$ рівно $a_d$ операцій повинні мати відстань $d$.

Можна показати, що оптимальна послідовність із щонайбільше $5n$ операцій завжди існує. Якщо існує кілька коректних послідовностей операцій, ви можете вивести будь-яку з них.

Приклади

Вхідні дані 1

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

Вихідні дані 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

Примітка

У першому прикладі Маленька Блакитна Рибка міняє місцями позиції $1$ і $3$. Це сортує перестановку за одну операцію з відстанню $2$.

У другому прикладі однією з оптимальних послідовностей є $(1, 4)$, $(2, 4)$, $(1, 4)$. Відстані дорівнюють $3$, $2$ та $3$, тому отримана послідовність дорівнює $(0, 1, 2)$.

У третьому прикладі однією з оптимальних послідовностей є $(2, 4)$, $(1, 4)$, $(1, 3)$, $(1, 4)$, $(2, 4)$. Кількості операцій за відстанями дорівнюють $(0, 3, 2)$.