CFCF2158F2.Distinct GCDs (Hard Version)

这是本题的困难版本。本版本与简单版本的区别在于 $n \leq 5000$。只有当你解决了所有版本后才能进行 hack。

传说中，高斯小时候老师曾经让全班算 $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$），并满足相邻元素的 最大公约数（GCD） 两两互不相同。形式化地讲，

$\gcd(a_i, a_{i+1}) \neq \gcd(a_j, a_{j+1})$ 对于所有 $1 \leq i < j < n$ 都成立。

此外，序列 $a$ 应使得不同元素的数量尽可能少。

每组测试数据包含多组测试用例。第一行为测试用例个数 $t$（$1 \leq t \leq 200$）。每组测试用例仅一行，包含单个整数 $n$（$2 \leq n \leq 5000$），表示所需构造的序列长度。

对于每个测试用例，输出 $n$ 个空格分隔的正整数 $a_1, a_2, \ldots, a_n$，保证 $1 \leq a_i \leq 10^{18}$ 并满足题中的所有条件。如果有多种方案，可以输出任意一种。

可以证明，在题目约束范围内，总是存在解。

对于第二个测试用例，相邻元素的最大公约数为 $[\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]$，均不相同。

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