Turtle and Multiplication
Contest: Codeforces Round 949 (Div. 2)
Difficulty rating: 2400
Tags: constructive algorithms, dfs and similar, graphs, number theory

Turtle just learned how to multiply two integers in his math class, and he was very excited.

Then Piggy gave him an integer $$$n$$$, and asked him to construct a sequence $$$a_1, a_2, \ldots, a_n$$$ consisting of integers which satisfied the following conditions:

- For all $$$1 \le i \le n$$$, $$$1 \le a_i \le 3 \cdot 10^5$$$.
- For all $$$1 \le i < j \le n - 1$$$, $$$a_i \cdot a_{i + 1} \ne a_j \cdot a_{j + 1}$$$.

Of all such sequences, Piggy asked Turtle to find the one with the minimum number of distinct elements.

Turtle definitely could not solve the problem, so please help him!

Input format:
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$2 \le n \le 10^6$$$) — the length of the sequence $$$a$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^6$$$.

Output format:
For each test case, output $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ — the elements of the sequence $$$a$$$.

If there are multiple answers, print any of them.

Constraints:
Time limit: 3.0 s
Memory limit: 512.0 MB

Note:
In the third test case, $$$a = [3, 4, 2, 6]$$$ violates the second condition since $$$a_1 \cdot a_2 = a_3 \cdot a_4$$$. $$$a = [2, 3, 4, 4]$$$ satisfy the conditions but its number of distinct elements isn't minimum.

Example input:
3
2
3
4

Example output:
114514 114514
1 2 2
3 3 4 4

Editorial:
The necessary condition for $$$a_i \cdot a_{i + 1} = a_j \cdot a_{j + 1}$$$ is that the unordered pairs $$$(a_i, a_{i + 1})$$$ and $$$(a_j, a_{j + 1})$$$ are identical. In fact, if $$$a_i$$$ are all prime numbers, then this necessary condition becomes sufficient.
If we consider $$$(a_i, a_{i + 1})$$$ as an edge, then the problem can be transformed into finding the undirected complete graph with the fewest nodes (where each node also has a self-loop) such that this complete graph contains a path of $$$n - 1$$$ edges without repeating any edge.
Next, we consider how to calculate the length of the longest path in a complete graph with a given number of vertices that does not repeat any edges.
Let the number of vertices in the complete graph be $$$m$$$. If $$$m$$$ is odd, then the degree of each node is even, so this graph contains an Eulerian path, and the path length is equal to the number of edges, which is $$$\frac{m(m + 1)}{2}$$$.
If $$$m$$$ is even, then the degree of each node is odd, and we need to remove some edges to make this graph contain an Eulerian path. It is easy to see that each edge removed can reduce the number of vertices with odd degrees by at most $$$2$$$, so we need to remove at least $$$\frac{m}{2} - 1$$$ edges. Removing the edges $$$(2, 3), (4, 5), \ldots, (m - 2, m - 1)$$$ will suffice, and the path length will be $$$\frac{m(m - 1)}{2} - \frac{m}{2} + 1 + m = \frac{m^2}{2} + 1$$$.
When $$$n = 10^6$$$, the smallest $$$m$$$ is $$$1415$$$, and the $$$1415$$$-th smallest prime number is $$$11807$$$, which satisfies $$$a_i \le 3 \cdot 10^5$$$.
We can use binary search to find the smallest $$$m$$$ and use Hierholzer's algorithm to find an Eulerian path in an undirected graph.
Time complexity: $$$O(n)$$$ per test case.