У Маленькой Голубой Рыбки есть перестановка $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)$.