For an integer sequence $a = [a_1, a_2, \ldots, a_n]$, we define $f(a)$ as the length of the longest subsequence$^{\text{∗}}$ of $a$ that is a palindrome$^{\text{†}}$.

Let $g(a)$ represent the number of subsequences of length $f(a)$ that are palindromes. In other words, $g(a)$ counts the number of palindromic subsequences in $a$ that have the maximum length.

Given an integer $n$, your task is to find any sequence $a$ of $n$ integers that satisfies the following conditions:

• $1 \le a_i \le n$ for all $1 \le i \le n$.
• $g(a) \gt n$

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

$^{\text{∗}}$A sequence $x$ is a subsequence of a sequence $y$ if $x$ can be obtained from $y$ by the deletion of several (possibly, zero or all) element from arbitrary positions. $^{\text{†}}$A palindrome is a sequence that reads the same from left to right as from right to left. For example, $[1, 2, 1, 3, 1, 2, 1]$, $[5, 5, 5, 5]$, and $[4, 3, 3, 4]$ are palindromes, while $[1, 2]$ and $[2, 3, 3, 3, 3]$ are not.

Input

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

The first line of each test case contains a single integer $n$ ($\color{red}{6} \le n \le 100$) — the length of the sequence.

Note that there are no constraints on the sum of $n$ over all test cases.

Output

For each test case, output $n$ integers $a_1, a_2, \ldots, a_n$, representing an array that satisfies the conditions.

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

Note

In the first example, one possible solution is $a = [1, 1, 2, 3, 1, 2]$. In this case, $f(a) = 3$ as the longest palindromic subsequence has length $3$. There are $7$ ways to choose a subsequence of length $3$ that is a palindrome, as shown below:

1. $[a_1, a_2, a_5] = [1, 1, 1]$
2. $[a_1, a_3, a_5] = [1, 2, 1]$
3. $[a_1, a_4, a_5] = [1, 3, 1]$
4. $[a_2, a_3, a_5] = [1, 2, 1]$
5. $[a_2, a_4, a_5] = [1, 3, 1]$
6. $[a_3, a_4, a_6] = [2, 3, 2]$
7. $[a_3, a_5, a_6] = [2, 1, 2]$

Therefore, $g(a) = 7$, which is greater than $n = 6$. Hence, $a = [1, 1, 2, 3, 1, 2]$ is a valid solution.

In the second example, one possible solution is $a = [7, 3, 3, 7, 5, 3, 7, 7, 3]$. In this case, $f(a) = 5$. There are $24$ ways to choose a subsequence of length $5$ that is a palindrome. Some examples are $[a_2, a_4, a_5, a_8, a_9] = [3, 7, 5, 7, 3]$ and $[a_1, a_4, a_6, a_7, a_8] = [7, 7, 3, 7, 7]$. Therefore, $g(a) = 24$, which is greater than $n = 9$. Hence, $a = [7, 3, 3, 7, 5, 3, 7, 7, 3]$ is a valid solution.

In the third example, $f(a) = 7$ and $g(a) = 190$, which is greater than $n = 15$.