E. Странные НОК операции
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дано целое число $$$n$$$, вы создаете массив $$$a$$$ из $$$n$$$ целых чисел, где $$$a_i = i$$$ для всех целых чисел $$$i$$$ в диапазоне $$$[1, n]$$$. Операция над этим массивом определена следующим образом:

  • Выберите в массиве три различных индекса $$$i$$$, $$$j$$$ и $$$k$$$ и присвойте $$$x = a_i$$$, $$$y = a_j$$$ и $$$z = a_k$$$.
  • Обновите массив следующим образом: $$$a_i = \operatorname{lcm}(y, z)$$$, $$$a_j = \operatorname{lcm}(x, z)$$$ и $$$a_k = \operatorname{lcm}(x, y)$$$, где $$$\operatorname{lcm}$$$ обозначает наименьшее общее кратное.
Ваша задача предоставить последовательность из не более чем $$$\lfloor \frac{n}{6} \rfloor + 5$$$ операций таких, что после применения этих операций, если вы возьмете множество, содержащее наибольший общий делитель (НОД) всех подпоследовательностей размера больше $$$1$$$, то каждое число от $$$1$$$ до $$$n$$$ должно принадлежать этому множеству.

После операций должно выполняться $$$a_i \le 10^{18}$$$ для всех $$$1 \le i \le n$$$.

Можно показать, что ответ всегда существует.

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

В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^2$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

В единственной строке каждого набора тестовых данных содержится одно целое число $$$n$$$ ($$$3 \leq n \leq 3 \cdot 10^{4}$$$) — длина массива.

Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$3 \cdot 10^{4}$$$.

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

Первая строка должна содержать целое число $$$k$$$ ($$$0 \leq k \leq \lfloor \frac{n}{6} \rfloor + 5$$$) — где $$$k$$$ обозначает число операций.

Следующие $$$k$$$ строк должны содержать описание операций, то есть $$$3$$$ различных целых числа $$$i$$$, $$$j$$$ и $$$k$$$, где $$$1 \leq i, j, k \leq n$$$.

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

В третьем наборе входных данных $$$a = [1, 2, 3, 4, 5, 6, 7]$$$.

Первая операция:

$$$i = 3$$$, $$$j = 5$$$, $$$k = 7$$$

$$$x = 3$$$, $$$y = 5$$$, $$$z = 7$$$.

$$$a = [1, 2, \operatorname{lcm}(y,z), 4, \operatorname{lcm}(x,z), 6, \operatorname{lcm}(x,y)]$$$ = $$$[1, 2, \color{red}{35}, 4, \color{red}{21}, 6, \color{red}{15}]$$$.

Вторая операция:

$$$i = 5$$$, $$$j = 6$$$, $$$k = 7$$$

$$$x = 21$$$, $$$y = 6$$$, $$$z = 15$$$.

$$$a = [1, 2, 35, 4, \operatorname{lcm}(y,z), \operatorname{lcm}(x,z), \operatorname{lcm}(x,y)]$$$ = $$$[1, 2, 35, 4, \color{red}{30}, \color{red}{105}, \color{red}{42}]$$$.

Третья операция:

$$$i = 2$$$, $$$j = 3$$$, $$$k = 4$$$

$$$x = 2$$$, $$$y = 35$$$, $$$z = 4$$$.

$$$a = [1, \operatorname{lcm}(y,z), \operatorname{lcm}(x,z), \operatorname{lcm}(x,y), 30, 105, 42]$$$ = $$$[1, \color{red}{140}, \color{red}{4}, \color{red}{70}, 30, 105, 42]$$$.

GCD равное $$$i$$$ может быть получено используя следующие подпоследовательности:

$$$\gcd(a_1, a_2) = \gcd(1, 140) = 1$$$

$$$\gcd(a_3, a_4) = \gcd(4, 70) = 2$$$

$$$\gcd(a_5, a_6, a_7) = \gcd(30, 105, 42) = 3$$$

$$$\gcd(a_2, a_3) = \gcd(140, 4) = 4$$$

$$$\gcd(a_2, a_4, a_5, a_6) = \gcd(140, 70, 30, 105) = 5$$$

$$$\gcd(a_5, a_7) = \gcd(30, 42) = 6$$$

$$$\gcd(a_2, a_4, a_6, a_7) = \gcd(140, 70, 105, 42) = 7$$$