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$$$.

Input

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$$$.

Output

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

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$$$.

The 67th OEIS Problem

Examples