F2. Различные НОДы (сложная версия)
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Это сложная версия задачи. Отличие между версиями заключается в том, что в этой версии $$$n \leq 5000$$$. Вы можете делать взломы только в том случае, если решили все версии этой задачи.

Согласно легенде, когда Гаусс был молодым школьником, его учитель дал классу задание сложить целые числа от $$$1$$$ до $$$100$$$, вероятно, чтобы занять их на некоторое время. Однако юный Гаусс быстро придумал формулу $$$\text{sum} = \frac{n(n+1)}{2}$$$ и нашёл ответ всего за несколько мгновений. Спустя века Гаусс появляется перед вами в кошмаре с пугающей задачей...

Вам дано целое положительное число $$$n$$$, найдите последовательность целых чисел $$$[a_1, a_2, \ldots, a_n]$$$ такую, что $$$1 \leq a_i \leq 10^{18}$$$ для всех $$$1 \leq i \leq n$$$, и все НОДы парно соседних элементов $$$a$$$ различны. Формально,

$$$\gcd(a_i, a_{i+1}) \neq \gcd(a_j, a_{j+1})$$$ для всех $$$1 \leq i \lt j \lt n$$$

Кроме того, $$$a$$$ должна иметь минимально возможное количество различных элементов.

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

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

Первая и единственная строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$2 \leq n \leq 5000$$$) — размер искомой последовательности.

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

Для каждого набора входных данных выведите на отдельной строке $$$n$$$ целых положительных чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^{18}$$$), разделённых пробелом, которые удовлетворяют условию задачи. Если существует несколько решений, выведите любое из них.

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

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

Для второго набора входных данных НОДы соседних элементов равны $$$[\gcd(1, 4), \gcd(4, 4), \gcd(4, 6), \gcd(6, 6)] = [1, 4, 2, 6]$$$, все из которых различны.

Для третьего набора входных данных НОДы соседних элементов равны $$$[\gcd(4, 4), \gcd(4, 6), \gcd(6, 6), \gcd(6, 9), \gcd(9, 9), \gcd(9, 4)] = [4, 2, 6, 3, 9, 1]$$$, все из которых различны.

Для каждого набора входных данных можно доказать, что не существует последовательности с меньшим количеством различных элементов, такой что все соседние НОДы различны.