Пожалуйста, подпишитесь на официальный канал Codeforces в Telegram по ссылке https://t.me/codeforces_official. ×

D. Деление с округлением вверх
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам задан массив $$$a_1, a_2, \dots, a_n$$$, в котором $$$a_i = i$$$.

За один шаг, вы можете выбрать две позиции $$$x$$$ и $$$y$$$ ($$$x \neq y$$$) и присвоить $$$a_x = \left\lceil \frac{a_x}{a_y} \right\rceil$$$ (деление с округлением вверх).

Ваша задача: сделать так, чтобы массив $$$a$$$ состоял из $$$n - 1$$$ единиц и $$$1$$$-й двойки за не более чем $$$n + 5$$$ шагов. Заметим, что не нужно минимизировать количество шагов.

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

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

В первой и единственной строке каждого набора задано одно целое число $$$n$$$ ($$$3 \le n \le 2 \cdot 10^5$$$) — длина массива $$$a$$$.

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

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

Для каждого набора входных данных, выведите список операций, который сделает так, что массив $$$a$$$ станет состоять из $$$n - 1$$$ единиц и $$$1$$$-й двойки, в следующем формате: сначала, выведите одно число $$$m$$$ ($$$m \le n + 5$$$) — количество операций; далее выведите $$$m$$$ пар чисел $$$x$$$ и $$$y$$$ ($$$1 \le x, y \le n$$$; $$$x \neq y$$$) ($$$x$$$ может быть как больше, так и меньше $$$y$$$) — выбранные позиции на соответствующем шаге.

Можно доказать, что для заданных ограничений всегда возможно найти некоторый список операций.

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

В первом наборе входных данных, у вас есть массив $$$a = [1, 2, 3]$$$. Вы можете сделать, например, следующее:

  1. выберем $$$3$$$, $$$2$$$: $$$a_3 = \left\lceil \frac{a_3}{a_2} \right\rceil = 2$$$ и массив $$$a = [1, 2, 2]$$$;
  2. выберем $$$3$$$, $$$2$$$: $$$a_3 = \left\lceil \frac{2}{2} \right\rceil = 1$$$ и массив $$$a = [1, 2, 1]$$$.
Вы получили массив с $$$2$$$ единицами и $$$1$$$ двойкой за $$$2$$$ шага.

Во втором наборе, $$$a = [1, 2, 3, 4]$$$. Вы можете, например, сделать следующее:

  1. выберем $$$3$$$, $$$4$$$: $$$a_3 = \left\lceil \frac{3}{4} \right\rceil = 1$$$ и массив $$$a = [1, 2, 1, 4]$$$;
  2. выберем $$$4$$$, $$$2$$$: $$$a_4 = \left\lceil \frac{4}{2} \right\rceil = 2$$$ и массив $$$a = [1, 2, 1, 2]$$$;
  3. выберем $$$4$$$, $$$2$$$: $$$a_4 = \left\lceil \frac{2}{2} \right\rceil = 1$$$ и массив $$$a = [1, 2, 1, 1]$$$.