CF2158F2.Distinct GCDs (Hard Version)

This is the hard version of the problem. The difference between the versions is that in this version, $n \leq 5000$. You can hack only if you solved all versions of this problem.

Legend has it that when Gauss was a young schoolboy, his teacher tasked the class with summing the integers from $1$ to $100$, likely as a way to keep them occupied for a while. However, young Gauss quickly came up with the formula $\text{sum} = \frac{n(n+1)}{2}$ and found the answer in mere moments. Centuries later, Gauss appears before you in a nightmare with a daunting task...

You are given a positive integer $n$, find a sequence of integers $[a_1, a_2, \ldots, a_n]$ such that $1 \leq a_i \leq 10^{18}$ for all $1 \leq i \leq n$, and the GCDs of pairwise adjacent elements of $a$ are all distinct. Formally,

$\gcd(a_i, a_{i+1}) \neq \gcd(a_j, a_{j+1})$ for each $1 \leq i \lt j \lt n$

Additionally, $a$ should have the minimum possible number of distinct elements.

这是该问题的困难版本。两个版本的区别在于，在本版本中，$n \leq 5000$。仅当您解决了该问题的所有版本时，才可进行 Hack。

传说高斯尚为小学生时，他的老师曾要求全班同学计算从 $1$ 到 $100$ 的所有整数之和，这很可能是为了让他们暂时安静下来。然而，年少的高斯迅速推导出了公式 $\text{sum} = \frac{n(n+1)}{2}$，并在片刻之间就得出了答案。几个世纪之后，高斯却在你的噩梦中现身，并交给你一项艰巨的任务……

给定一个正整数 $n$，请构造一个整数序列 $[a_1, a_2, \ldots, a_n]$，使得对所有 $1 \leq i \leq n$ 均满足 $1 \leq a_i \leq 10^{18}$，且序列 $a$ 中所有相邻元素对的最大公约数（GCD）互不相同。形式化地，

对每个 $1 \leq i \lt j \lt n$，均有 $\gcd(a_i, a_{i+1}) \neq \gcd(a_j, a_{j+1})$。

此外，序列 $a$ 中不同元素的个数应尽可能少。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 200$). The description of the test cases follows.

The first and only line of each test case contains a single integer $n$ ($2 \leq n \leq 5000$) — the size of the sequence to be found.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 200$）。随后是测试用例的描述。

每个测试用例仅有一行，包含一个整数 $n$（$2 \leq n \leq 5000$）—— 即待求序列的长度。

For each test case, output $n$ space-separated positive integers $a_1, a_2, \ldots, a_n$ ($1 \leq a_i \leq 10^{18}$) on a new line that satisfy the condition in the statement. If there are multiple solutions, print any of them.

It can be proven that under the problem constraints, a solution always exists.

对于每个测试用例，在一行内输出 $n$ 个以空格分隔的正整数 $a_1, a_2, \ldots, a_n$（$1 \leq a_i \leq 10^{18}$），使其满足题目陈述中的条件。若存在多个解，输出任意一个即可。

可以证明，在本题的约束条件下，解总是存在的。

For the second test case, the GCDs of adjacent elements are $[\gcd(1, 4), \gcd(4, 4), \gcd(4, 6), \gcd(6, 6)] = [1, 4, 2, 6]$, all of which are distinct.

For the third test case, the GCDs of adjacent elements are $[\gcd(4, 4), \gcd(4, 6), \gcd(6, 6), \gcd(6, 9), \gcd(9, 9), \gcd(9, 4)] = [4, 2, 6, 3, 9, 1]$, all of which are distinct.

For each test case, it can be proven that no sequence with fewer distinct elements exists such that all adjacent GCDs are distinct.

对于第二个测试用例，相邻元素的最大公约数（GCD）序列为 $[\gcd(1, 4), \gcd(4, 4), \gcd(4, 6), \gcd(6, 6)] = [1, 4, 2, 6]$，其中所有值互不相同。

对于第三个测试用例，相邻元素的最大公约数（GCD）序列为 $[\gcd(4, 4), \gcd(4, 6), \gcd(6, 6), \gcd(6, 9), \gcd(9, 9), \gcd(9, 4)] = [4, 2, 6, 3, 9, 1]$，其中所有值互不相同。

对于每个测试用例，均可证明：不存在元素种类数更少的序列，使得所有相邻元素的最大公约数互不相同。