Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

The problem statement has recently been changed. View the changes.

×
A. Omkar and Completion

time limit per test

1 secondmemory limit per test

256 megabytesinput

standard inputoutput

standard outputYou have been blessed as a child of Omkar. To express your gratitude, please solve this problem for Omkar!

An array $$$a$$$ of length $$$n$$$ is called complete if all elements are positive and don't exceed $$$1000$$$, and for all indices $$$x$$$,$$$y$$$,$$$z$$$ ($$$1 \leq x,y,z \leq n$$$), $$$a_{x}+a_{y} \neq a_{z}$$$ (not necessarily distinct).

You are given one integer $$$n$$$. Please find any complete array of length $$$n$$$. It is guaranteed that under given constraints such array exists.

Input

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

The only line of each test case contains one integer $$$n$$$ ($$$1 \leq n \leq 1000$$$).

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$1000$$$.

Output

For each test case, print a complete array on a single line. All elements have to be integers between $$$1$$$ and $$$1000$$$ and for all indices $$$x$$$,$$$y$$$,$$$z$$$ ($$$1 \leq x,y,z \leq n$$$) (not necessarily distinct), $$$a_{x}+a_{y} \neq a_{z}$$$ must hold.

If multiple solutions exist, you may print any.

Example

Input

2 5 4

Output

1 5 3 77 12 384 384 44 44

Note

It can be shown that the outputs above are valid for each test case. For example, $$$44+44 \neq 384$$$.

Below are some examples of arrays that are NOT complete for the 1st test case:

$$$[1,2,3,4,5]$$$

Notice that $$$a_{1}+a_{2} = a_{3}$$$.

$$$[1,3000,1,300,1]$$$

Notice that $$$a_{2} = 3000 > 1000$$$.

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Sep/18/2021 01:10:15 (i1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|