C. Aziza Supermarket Heist
time limit per test
3 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

you and your friends came up with a reasonable plan: Rob a Aziza supermarket.

However, the store has installed a new security system to prevent such attempts.

To bypass the security, you must generate a key consisting of $$$n$$$ positive integers ( $$$0 \lt a_i \lt 10^9$$$ ) where the sum of the numbers is equal to their product.

Formally, you need to find a sequence $$$a_1, a_2, \dots, a_n$$$ ( where $$$a_i \gt 0$$$ and $$$a_i \lt 10^9$$$ for all i ) such that: $$$$$$ \sum_{i=1}^{n} a_i = \prod_{i=1}^{n} a_i $$$$$$

Your task is simple: for a given $$$n$$$, output any sequence of $$$n$$$ positive integers satisfying this condition.

It is guaranteed that a solution always exists for all given $$$n$$$.

Input

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

The only line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 10^5$$$).

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

Output

For each test case, output $$$n$$$ space-separated integers that satisfy the condition.

If there are multiple solutions, print any of them.

Example
Input
3
1
2
3
Output
1
2 2
1 2 3