H. Codeforces Heuristic Contest 001
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
1024 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

Дана сетка из $$$3n \times 3n$$$ точек, состоящая из всех целых точек $$$(x,y)$$$, таких что $$$1 \le x,y \le 3n$$$.

Найдите максимальный набор треугольников, удовлетворяющий следующим условиям:

  • Каждый треугольник имеет свои вершины на ровно трех точках на сетке.
  • Каждый треугольник имеет площадь ровно $$$\frac{1}{2}$$$. Обратите внимание, что они не обязательно должны быть прямоугольными треугольниками.
  • Никакие два треугольника не пересекаются, включая их вершины.

Если существует несколько таких максимальных наборов треугольников, вы можете вывести любой из них.

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

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

Единственная строка каждого набора содержит одно целое число $$$n$$$ ($$$1 \le n \le 166$$$).

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

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

Выведите максимальный размер $$$m$$$ набора треугольников в одной строке ($$$0 \le m \le 3n^2$$$).

Затем выведите $$$m$$$ строк в следующем формате:

  • $$$x_{i,1}\;y_{i,1}\;x_{i,2}\;y_{i,2}\;x_{i,3}\;y_{i,3}$$$: Вершины $$$i$$$-го треугольника это $$$(x_{i,1},y_{i,1})$$$, $$$(x_{i,2},y_{i,2})$$$, $$$(x_{i,3},y_{i,3})$$$.

Вы можете выводить вершины одного треугольника в любом порядке (по часовой стрелке или против часовой стрелки).

Ваш вывод будет принят, если он удовлетворяет всем условиям и указанный максимальный размер верен.

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

В первом примере вывод содержит $$$2$$$ треугольника, как показано на следующем изображении:

Во втором примере вывод содержит $$$12$$$ треугольников, как показано на изображении слева:

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