CF2056C Palindromic Subsequences

对于序列 $ a = [a_1, a_2, \ldots, a_n] $，定义 $ f(a) $ 为最长回文子序列（可以不连续）的长度，$ g(a) $ 为长度为 $ f(a) $ 的回文子序列的数量，即最长回文子序列的数量。 给定整数 $ n $，构造一个长度为 $ n $ 的序列 $ a $，使得： - $\forall 1 \le i \le n $，$ 1 \le a_i \le n $； - $ g(a) > n $。 可以证明这样的序列一定存在。

本题多测。输入的第一行为一个正整数 $ t $（$ 1 \le t \le 100 $），表示测试数据组数。 对于每组测试数据，输入一行一个正整数 $ n $（$ \color{red}{6}\color{default} \le n \le 100 $），表示序列的长度。 对于一个测试点中所有测试数据中的 $n$ 之和没有限制。

对于每组测试数据，输出 $ n $ 个正整数 $ a_1, a_2, \ldots, a_n $ ，表示一个符合要求的序列。输出任意一组解即可。

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