C. Palindromic Subsequences
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

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) > 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.

Example
Input
3
6
9
15
Output
1 1 2 3 1 2
7 3 3 7 5 3 7 7 3
15 8 8 8 15 5 8 1 15 5 8 15 15 15 8
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$$$.