N. Primemas
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given an integer $$$n$$$. Output an integer array $$$a$$$ of length $$$n$$$ such that:

  • $$$1 \le a_i \le 10^9$$$ ($$$1 \le i \le n$$$)
  • For all $$$1 \le j \lt k \le n$$$, $$$a_j + a_k$$$ is a prime number

It can be shown that under the given constraints, a solution always exists.

Input

Each test consists of multiple test cases.

The first line of input contains a single integer $$$t$$$ ($$$1 \le t \le 500$$$) — the number of test cases.

Each test case consists of a single line containing an integer $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — the required length of the array.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output

For each test case, output $$$n$$$ integers $$$a_1, \ldots, a_n$$$ satisfying the above constraints.

If there are multiple solutions, you may print any.

Example
Input
2
2
3
Output
6 7
1 66 1
Note

In the first test case, we have $$$a_1 + a_2 = 13$$$, and $$$13$$$ is a prime number.

In the second test case, we have $$$a_1 + a_2 = 67$$$, $$$a_1 + a_3 = 2$$$, and $$$a_2 + a_3 = 67$$$, all of which are prime.