E. Что это?
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Луноход наконец-то достиг поверхности планеты X. Приземлившись, он встретился с препятствием, на котором записана перестановка $$$p$$$ длины $$$n$$$. Учёным удалось выяснить, что для того, чтобы преодолеть препятствие, необходимо добиться того, чтобы $$$p$$$ стала тождественной (должно выполняться $$$p_i = i$$$ для всех $$$i$$$).

К сожалению, учёные не могут управлять роботом на расстоянии. Из-за этого единственный способ сделать $$$p$$$ тождественной — применить к $$$p$$$ следующую операцию несколько раз:

  • Выбрать две позиции $$$i$$$ и $$$j$$$ ($$$i \neq j$$$), такие, что $$$p_j = i$$$ и поменять местами значения $$$p_i$$$ и $$$p_j$$$. Операция занимает $$$(j - i)^2$$$ секунд из-за выполнения её роботом.

Позиции $$$i$$$ и $$$j$$$ выбирает робот (учёные не могут влиять на его выбор). Он будет применять эту операцию до тех пор, пока $$$p$$$ не станет тождественной. Можно показать, что не более чем через $$$n$$$ операций (вне зависимости от выбора $$$i$$$ и $$$j$$$) перестановка станет тождественной.

Учёные попросили Вас найти максимальное время, за которое робот сделает $$$p$$$ тождественной (т.е. худший возможный вариант развития событий), чтобы они могли отдохнуть или же отправить более продвинутый луноход на планету X. Также учёные попросили Вас предоставить пример перестановки $$$p$$$ и последовательности операций робота, которые максимизируют ответ.

Для лучшего понимания условия обратитесь к примечаниям к примеру.

Входные данные

В первой строке задано одно целое число $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — количество наборов входных данных.

В каждой из следующих $$$t$$$ строк задано одно целое число $$$n$$$ ($$$2 \leq n \leq 10^5$$$) — длина перестановки $$$p$$$.

Обратите внимание, что перестановка $$$p$$$ Вам не дана, и Вам нужно найти максимальное время работы робота по всем перестановкам длины $$$n$$$.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$10^5$$$.

Выходные данные

Для каждого набора входных данных, в первой строке выведите максимальное время работы робота (в секундах).

Во второй строке выведите исходную перестановку $$$p$$$, на которой достигается Ваш ответ.

В третьей строке выведите количество операций $$$m \leq n$$$, которое робот сделает в Вашем примере.

В следующих $$$m$$$ строках выведите по два числа $$$i$$$ и $$$j$$$ — индексы позиций, которые робот выбирает на этой операции. Обратите внимание, что $$$p_j = i$$$ должно выполняться (в момент операции).

Пример
Входные данные
3
2
3
3
Выходные данные
1
2 1
1
2 1
5
2 3 1
2
1 3
3 2
5
2 3 1
2
1 3
2 3
Примечание

Для $$$n = 2$$$, $$$p$$$ может быть равна $$$[1, 2]$$$ или $$$[2, 1]$$$. В первом случае $$$p$$$ уже является тождественной, а во втором случае робот сделает её тождественной за $$$1$$$ секунду вне зависимости от выбора $$$i$$$ и $$$j$$$ на первой операции.

Для $$$n = 3$$$, $$$p$$$ может оказаться равна $$$[2, 3, 1]$$$.

  • Если робот выберет $$$i = 3, j = 2$$$ на первой операции, то через одну секунду $$$p$$$ станет равна $$$[2, 1, 3]$$$. Теперь робот может выбрать только $$$i = 1, j = 2$$$ или $$$i = 2, j = 1$$$. В любом из этих случаев, $$$p$$$ станет тождественной через ещё одну секунду (всего — $$$2$$$ секунды).
  • Если робот выберет $$$i = 1, j = 3$$$ на первой операции, то через четыре секунды $$$p$$$ станет равна $$$[1, 3, 2]$$$. Вне зависимости от выбора $$$i$$$ и $$$j$$$ на второй операции, $$$p$$$ станет тождественной через пять секунд работы робота.

Можно показать, что робот всегда сможет завершить работу с перестановкой длины $$$3$$$ за $$$5$$$ или меньше секунд.