У 2077 році складати задачі стало просто. Роботи генерують задачу, задаючи декілька випадкових операцій, а потім самі її розв'язують. Автору задачі потрібно лише перевірити, чи є задача коректною.

Ось задача з 2077 року:

Дано перестановку $p_1, p_2, \dots, p_n$, причому гарантується, що $n$ є парним. Ви хочете відсортувати цю перестановку, використовуючи лише один тип операцій:

• FakeSort(l,r): Ви повинні гарантувати, що $r - l + 1$ є парним. Нехай $k = r - l + 1$, тоді $k/2$ найбільших елементів та $k/2$ найменших елементів у неперервній підпослідовності $p_l, p_{l+1}, \dots, p_r$ будуть відсортовані незалежно один від одного. Іншими словами, нехай $L_1, L_2, \dots, L_{k/2}$ — індекси $k/2$ найбільших чисел, а $S_1, S_2, \dots, S_{k/2}$ — індекси $k/2$ найменших чисел. Спочатку ми сортуємо числа на індексах $L_1 \sim L_{k/2}$, а потім сортуємо числа на індексах $S_1 \sim S_{k/2}$.

Ось конкретний приклад: припустімо, що перестановка має вигляд $p = \{2, 5, 7, 1, 8, 6, 4, 3\}$. Якщо ми викличемо FakeSort(2,7):

• $k = r - l + 1 = 6$. Неперервна підпослідовність $p_l, p_{l+1}, \dots, p_r$ дорівнює $\{5, 7, 1, 8, 6, 4\}$; ми незалежно відсортуємо $3$ найбільші числа та $3$ найменші числа цієї послідовності.
• $p = \{2, 5, \mathbf{7}, 1, \mathbf{8}, \mathbf{6}, 4, 3\}$; $3$ найбільші числа виділено жирним шрифтом. Після сортування вони стають $p = \{2, 5, \mathbf{6}, 1, \mathbf{7}, \mathbf{8}, 4, 3\}$.
• $p = \{2, \mathbf{5}, 6, \mathbf{1}, 7, 8, \mathbf{4}, 3\}$; $3$ найменші числа виділено жирним шрифтом. Після сортування вони стають $p = \{2, \mathbf{1}, 6, \mathbf{4}, 7, 8, \mathbf{5}, 3\}$.

Отже, $p = \{2, 5, 7, 1, 8, 6, 4, 3\}$ після FakeSort(2,7) перетворюється на $\{2, 1, 6, 4, 7, 8, 5, 3\}$.

Будь ласка, використайте не більше $114$ операцій, щоб відсортувати перестановку, або визначте, що це неможливо. Можна довести, що якщо перестановку можна відсортувати за допомогою цієї операції, то існує спосіб зробити це не більше ніж за $114$ операцій.

Вхідні дані

Вхідні дані містять декілька наборів тестових даних. Перший рядок містить ціле число $T$ ($1 \le T \le 10^3$) — кількість наборів тестових даних.

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

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

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

Вихідні дані

Для кожного набору тестових даних, якщо відсортувати перестановку неможливо, виведіть $-1$.

Інакше виведіть ціле число $k$ ($0 \le k \le 114$), що позначає кількість використаних операцій.

У наступних $k$ рядках виведіть по два числа $l, r$ ($1 \le l \le r \le n$, $r - l + 1$ є парним) у кожному рядку, що позначають виконання FakeSort(l,r).

Приклади

Приклад вводу 1

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

Приклад виводу 1

1
1 4
-1
2
4 7
1 6