Изменения рейтингов за последние раунды временно удалены. Скоро они будут возвращены. ×

D. Черепаха и умножение
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Черепаха только что научилась умножать два целых числа на уроке математики и была очень взволнована.

Затем Свинка дала ей целое число $$$n$$$ и попросила построить последовательность $$$a_1, a_2, \ldots, a_n$$$, состоящую из целых чисел, которые удовлетворяли бы следующим условиям:

  • Для всех $$$1 \le i \le n$$$, $$$1 \le a_i \le 3 \cdot 10^5$$$.
  • Для всех $$$1 \le i < j \le n - 1$$$, $$$a_i \cdot a_{i + 1} \ne a_j \cdot a_{j + 1}$$$.

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

Черепаха определенно не смогла бы решить задачу, поэтому пожалуйста, помогите ей!

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

Каждый тест содержит несколько тестовых случаев. Первая строка содержит количество тестов $$$t$$$ ($$$1 \le t \le 10^4$$$). Затем следует описание тестов.

Первая строка каждого теста содержит одно целое число $$$n$$$ ($$$2 \le n \le 10^6$$$) — длина последовательности $$$a$$$.

Гарантируется, что сумма $$$n$$$ по всем тестовым случаям не превышает $$$10^6$$$.

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

Для каждого тестового случая выведите $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ — элементы последовательности $$$a$$$.

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

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

В третьем тестовом случае $$$a = [3, 4, 2, 6]$$$ нарушает второе условие, так как $$$a_1 \cdot a_2 = a_3 \cdot a_4$$$. $$$a = [2, 3, 4, 4]$$$ удовлетворяет условиям, но количество различных элементов в нем не минимально.