Statement : D. The 67th OEIS Problem

Macaque, being a terrible problemsetter, decided to search for funny sequences on the OEIS$^{\text{∗}}$ one day, so he could gain inspiration for his doomed problemsetting job for the Pan-Mammalian Olympiad in Informatics (PMOI). To his delight, he found one, and thought it would be funny to make you, his loyal tester, solve it:

Construct a sequence $a$ containing $n$ integers such that $\operatorname{gcd}(a_i, a_{i+1})$ $^{\text{†}}$ is distinct over all $1 \leq i \leq n - 1$. It is guaranteed that at least one sequence $a$ exists.

$^{\text{∗}}$Online Encyclopedia of Integer Sequences, the favourite website of math nerds, overly astute testers, and insufficiently rigorous coordinators.

$^{\text{†}}$$\operatorname{gcd}(x,y)$ refers to the greatest common divisor of integers $x$ and $y$.

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

The following $t$ lines contain one integer $n$ ($2 \leq n \leq 10^4$) — the desired length of the sequence.

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

For each query, output your answer — a sequence $a$ of $n$ space-separated integers ($1 \le a_i \le 10^{18}$).

Input

2
3
5

Output

1 6 2
134 67 69 207 414

Note

In the first test case, the sequence $[1, 6, 2]$ is a possible answer. This is because $\gcd(1, 6)$ is not equal to $\gcd(6, 2)$.

In the second test case, the sequence $[134, 67, 69, 207, 414]$ is a possible answer. This is because the values of $\gcd(a_i, a_{i+1})$ for all $i$ between $1$ and $n-1$ are distinct. For reference, they are $67$, $1$, $69$ and $207$.