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:

$$$[a_1, a_2, a_5] = [1, 1, 1]$$$
$$$[a_1, a_3, a_5] = [1, 2, 1]$$$
$$$[a_1, a_4, a_5] = [1, 3, 1]$$$
$$$[a_2, a_3, a_5] = [1, 2, 1]$$$
$$$[a_2, a_4, a_5] = [1, 3, 1]$$$
$$$[a_3, a_4, a_6] = [2, 3, 2]$$$
$$$[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$$$.

Palindromic Subsequences

Examples