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.

Input

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.

Output

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.

Note

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.