Фран и София стали большими поклонниками битв роботов за ауру, поэтому решили устроить собственный турнир роботов за ауру. Поскольку София отлично разбирается в роботах, Франу понадобится ваша помощь, чтобы выиграть чемпионат.
Матч турнира проходит на доске $$$n \times n$$$. Строки пронумерованы снизу вверх, а столбцы — слева направо, поэтому $$$(1, 1)$$$ — левый нижний угол, а $$$(n, n)$$$ — правый верхний. Робот противника спрятан в некоторой неизвестной клетке $$$(i, j)$$$ и перемещается раз в секунду, но вы его не видите.
В начале каждой секунды $$$s$$$, прежде чем робот переместится, вы должны выбрать целое число $$$v$$$ такое, что $$$2 \le v \le 2n$$$, и выстрелить лазером вдоль диагонали
$$$$$$\{\, (r, c) \mid r + c = v \,\}.$$$$$$ Если робот в этот момент находится в клетке этой диагонали, лазер касается его, и вы немедленно побеждаете. В противном случае после выстрела, если робот сейчас находится в клетке $$$(r, c)$$$, он перемещается в одну из следующих клеток при условии, что она находится внутри доски:
Робот находится в клетке $$$(3,2)$$$ (его диагональ задаётся равенством $$$r+c=5$$$). Зелёный лазер проходит по диагонали $$$v=7$$$ и не касается робота. Робот действует против вас: он может начать в любой клетке и выбрать любую допустимую последовательность перемещений. Вам требуется вывести фиксированную последовательность из не более чем $$$3n$$$ диагоналей $$$v_1, v_2, \ldots, v_k$$$, такую, что независимо от начальной клетки робота и его перемещений хотя бы один лазер гарантированно коснётся его в некоторую секунду турнира.
Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 44$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
Единственная строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$2 \le n \le 100$$$) — размер доски.
Гарантируется, что сумма значений $$$n^3$$$ по всем наборам входных данных не превосходит $$$10^6$$$.
Для каждого набора входных данных выведите две строки. В первой строке выведите целое число $$$k$$$ ($$$1 \le k \le 3n$$$) — количество лазеров.
Во второй строке выведите $$$k$$$ целых чисел $$$v_1, v_2, \ldots, v_k$$$ ($$$2 \le v_i \le 2n$$$) — диагонали в порядке выстрелов.
Можно вывести любую допустимую последовательность.
223
3 3 3 3 3 4 4 4
При $$$n = 2$$$ подходит последовательность $$$3, 3, 3$$$. Первый лазер $$$3$$$ поражает робота на диагонали $$$r + c = 3$$$ (в клетках $$$(1, 2)$$$ и $$$(2, 1)$$$). На следующем ходу из клетки $$$(1, 1)$$$ робот обязательно перемещается на ту же диагональ, а из клетки $$$(2, 2)$$$ он вынужден двигаться так: $$$(2, 2) \to (1, 1) \to$$$ попадание на ту же диагональ. Второй и третий лазеры поражают робота в обоих случаях.
При $$$n = 3$$$ подходит последовательность $$$4, 4, 4$$$. Робота на диагонали $$$r + c = 4$$$ поражает первый лазер. С диагонали $$$r + c = 3$$$ или из клетки $$$(3, 3)$$$ любой ход ведёт на $$$r + c = 4$$$, поэтому робота поражает второй лазер. Из клетки $$$(1, 1)$$$ или с диагонали $$$r + c = 5$$$ любой ход ведёт на $$$r + c = 3$$$ или в клетку $$$(3, 3)$$$, поэтому робота поражает третий лазер.
