Dominant Sequence

题目描述

You are given an integer $n$.

Your task is to construct a sequence of positive integers $a_1,a_2,...,a_n$ such that for every segment $[l,r]$, there exists an index $i$ with $l \le i \le r$ satisfying $2a_i \gt a_l+a_{l+1}+...+a_r$.

In other words, every segment must contain an element which is strictly greater than half of the sum of this segment.

Additionally, every element of the sequence must not exceed $10^9$.

It can be proven that under the given constraints, a valid sequence always exists.

输入格式

The first line contains one integer $T$ ($1 \le T \le 10^4$), denoting the number of test cases.

Each test case contains one integer $n$ ($1 \le n \le 10^4$).

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

输出格式

For each test case, output $n$ integers $a_1,a_2,...,a_n$.

The sequence must satisfy $1 \le a_i \le 10^9$ for every $i$.

For every segment $[l,r]$, there must exist an index $i$ with $l \le i \le r$ such that $2a_i \gt a_l+a_{l+1}+...+a_r$.

If there are multiple valid answers, you may output any of them.

样例输入 #1

3
1
2
5

样例输出 #1

1
2 1
1 3 1 7 1