Kattis

Beautiful Primes

John Nash is a talented mathematician at Princeton. Due to his prolific contributions in academia, he was even recruited to the Pentagon at a young age to crack enemy encrypted telecommunication. In his first task, John was able to decipher the code mentally, much to the astonishment of other decrypters. In his everyday life, he is constantly looking for patterns in magazines to newspapers to keep his senses sharp.

Recently, he has been cracking away at a cryptography problem that involves prime numbers. Given a positive integer $N$, the puzzle needs him to produce a “beautiful" list of $N$ primes. A list of $N$ primes numbers is considered beautiful if each prime is at most $1\, 000\, 000$, and their product has exactly $N$ digits.

For example, if $N = 1$, then the list $[5]$ is beautiful because its length is $1$, and its product $5$ has $1$ digit.

For $N = 2$, the list $[3, 7]$ is beautiful because its product $3 \times 7 = 21$ has the required digit count of $2$.

For $N = 3$, the list $[5, 5, 7]$ is beautiful because its product $5 \times 5 \times 7 = 175$ has the required digit count of $3$.

John wants to practice his mental math and impress his colleagues. He needs you to write a program that helps him practice this interesting task. John Nash has a beautiful mind, so won’t you help him find some beautiful primes?

Input

The first line of input consists of a single integer $T$ ($1 \leq T \leq 50$), the number of test cases.
$T$ lines follow, each of which is a test case consisting of a single integer $N$ ($1 \leq N \leq 1\, 000$).

Output

For each test case, print, on a separate line, a list of $N$ space-delimited beautiful primes that are each no greater than $1\, 000\, 000$. The primes do not have to be distinct, and may be printed in any order. If there are multiple answers, you may print any of them.

Sample Input 1 Sample Output 1
3
1
2
3

5
3 7
5 5 7