C. Palindromic Subsequencestime limit per test2 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard 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.InputEach 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.OutputFor 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.ExampleInput36915Output1 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
NoteIn 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$$$.