В 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