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](https://en.wikipedia.org/wiki/Greatest_common_divisor) 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 < j < n $ Additionally, $ a $ should have the minimum possible number of distinct elements.

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.

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.

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.