AT_tupc2022_g All Pairs

正整数 $ N $ が与えられます。長さ $ M $ の正整数列 $ A $ は、次の条件を満たすとき**良い数列**であるといいます。 - 任意の整数の組 $ (x,y) $ $ (1\leq x\lt y\leq N) $ に対して、 $ (A_i,A_{i+1})=(x,y) $ または $ (A_i,A_{i+1})=(y,x) $ を満たす整数 $ i\ (1\leq i\leq M-1) $ が存在する。 長さ $ M $ が最小であるような良い数列のうち、辞書順最小のものを求めてください。 $ T $ 個のテストケースが与えられるので、それぞれについて答えを求めてください。

入力は以下の形式で標準入力から与えられる。 > $ T $ $ \mathrm{case}_1 $ $ \mathrm{case}_2 $ $ \vdots $ $ \mathrm{case}_T $ 各ケースは以下の形式で与えられる。 > $ N $

$ T $ 行出力せよ。 $ i $ 行目には $ i $ 番目のテストケースに対する答えとなる数列を $ A=(A_1,A_2,\ldots,A_M) $ として、 $ A_1,A_2,\ldots,A_M $ をこの順に空白区切りで一行で出力せよ。

### Sample Explanation 1 $ N=3 $ のとき、例えば $ A=(1,2,1,3,2) $ は良い数列であることが以下のように確かめられます。 - $ (x,y)=(1,2) $ について、 $ (A_1,A_2)=(x,y) $ を満たす。 - $ (x,y)=(1,3) $ について、 $ (A_3,A_4)=(x,y) $ を満たす。 - $ (x,y)=(2,3) $ について、 $ (A_4,A_5)=(y,x) $ を満たす。 他にも良い数列として $ (1,2,3,1), (1,2,3,1,100), (3,1,2,3) $ などが挙げられます。一方、 $ (1,2,3),(1,2,1,3) $ は良い数列ではありません。 長さが $ 3 $ 以下の良い数列は存在しないため、長さ $ 4 $ の良い数列のうち辞書順最小である $ (1,2,3,1) $ が求めるものです。 ### Constraints - $ 1\leq T\leq 99 $ - $ 2\leq N\leq 100 $ - 入力はすべて整数