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

Для целочисленной последовательности $$$a = [a_1, a_2, \ldots, a_n]$$$ определим $$$f(a)$$$ как длину самой длинной подпоследовательности$$$^{\text{∗}}$$$ из $$$a$$$, которая является палиндромом$$$^{\text{†}}$$$.

Пусть $$$g(a)$$$ обозначает число подпоследовательностей длины $$$f(a)$$$, которые являются палиндромами. Иными словами, $$$g(a)$$$ подсчитывает количество палиндромных подпоследовательностей в $$$a$$$, которые имеют максимальную длину.

Для данного числа $$$n$$$, ваша задача состоит в том, чтобы найти любую последовательность $$$a$$$ из $$$n$$$ целых чисел, которая удовлетворяет следующим условиям:

  • $$$1 \le a_i \le n$$$ для всех $$$1 \le i \le n$$$.
  • $$$g(a) > n$$$

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

$$$^{\text{∗}}$$$Последовательность $$$x$$$ является подпоследовательностью $$$y$$$, если $$$x$$$ может быть получена из $$$y$$$ удалением нескольких (возможно, ни одного или всех) элементов на произвольных позициях.

$$$^{\text{†}}$$$Палиндром — это последовательность, которая читается одинаково слева направо и справа налево. Например, $$$[1, 2, 1, 3, 1, 2, 1]$$$, $$$[5, 5, 5, 5]$$$, и $$$[4, 3, 3, 4]$$$ являются палиндромами, в то время как $$$[1, 2]$$$ и $$$[2, 3, 3, 3, 3]$$$ — нет.

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

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

Первая строка каждого набора входных данных содержит единственное целое число $$$n$$$ ($$$\color{red}{6} \le n \le 100$$$) — длина последовательности.

Обратите внимание, что нет дополнительного ограничения на сумму $$$n$$$ по всем наборам входных данных.

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

Для каждого набора входных данных выведите $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ — массив, удовлетворяющий условиям.

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

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

В первом примере одним из возможных решений является $$$a = [1, 1, 2, 3, 1, 2]$$$. В этом наборе входных данных $$$f(a) = 3$$$, поскольку самая длинная палиндромная подпоследовательность имеет длину $$$3$$$. Существует $$$7$$$ способов выбрать подпоследовательность длины $$$3$$$, которая является палиндромом, как показано ниже:

  1. $$$[a_1, a_2, a_5] = [1, 1, 1]$$$
  2. $$$[a_1, a_3, a_5] = [1, 2, 1]$$$
  3. $$$[a_1, a_4, a_5] = [1, 3, 1]$$$
  4. $$$[a_2, a_3, a_5] = [1, 2, 1]$$$
  5. $$$[a_2, a_4, a_5] = [1, 3, 1]$$$
  6. $$$[a_3, a_4, a_6] = [2, 3, 2]$$$
  7. $$$[a_3, a_5, a_6] = [2, 1, 2]$$$

$$$g(a) = 7$$$, что больше, чем $$$n = 6$$$. Следовательно, $$$a = [1, 1, 2, 3, 1, 2]$$$ — это верное решение.

Во втором примере одним из возможных решений является $$$a = [7, 3, 3, 7, 5, 3, 7, 7, 3]$$$. В этом наборе входных данных $$$f(a) = 5$$$. Существует $$$24$$$ способа выбрать подпоследовательность длины $$$5$$$, которая является палиндромом. Некоторыми примерами являются $$$[a_2, a_4, a_5, a_8, a_9] = [3, 7, 5, 7, 3]$$$ и $$$[a_1, a_4, a_6, a_7, a_8] = [7, 7, 3, 7, 7]$$$. Следовательно, $$$g(a) = 24$$$, что больше, чем $$$n = 9$$$. Следовательно, $$$a = [7, 3, 3, 7, 5, 3, 7, 7, 3]$$$ — это верное решение.

В третьем примере $$$f(a) = 7$$$ и $$$g(a) = 190$$$, что больше, чем $$$n = 15$$$.