AT_arc220_d [ARC220D] Long Trail

正整数 $ N $ が与えられます。 $ G $ を頂点 $ 1,2,\ldots,N $ からなる $ N $ 頂点 $ \displaystyle \frac{N(N-1)}2 $ 辺の完全無向グラフとします。 以下の条件を全て満たす $ G $ 上の trail $ (v_1,v_2,\ldots,v_k) $ を一つ求めてください。 - $ 1 \leq i \leq k-2 $ を満たす整数 $ i $ 全てについて、 $ |v_i - v_{i+2}| = 1 $ - $ \displaystyle \frac{(N-2)^2}2 \le k $ ただし、制約下でそのような trail が必ず存在することが証明できます。 trail とは？ 無向グラフ $ G $ 上の頂点列 $ (v_1,v_2,\ldots,v_k) $ が以下の条件を全て満たす時、 $ (v_1,v_2,\ldots,v_k) $ を $ G $ 上の trail であるとします。 - $ 1\le v_i\le N. $ - $ 1\le i\le k-1 $ に対し、頂点 $ v_i $ と頂点 $ v_{i+1} $ を結ぶ辺が存在する。 - $ 1\le i < j \le k-1 $ に対し、「頂点 $ v_i $ と頂点 $ v_{i+1} $ を結ぶ辺」と「頂点 $ v_j $ と頂点 $ v_{j+1} $ を結ぶ辺」は異なる。

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

各テストケースに対する答えを順に改行区切りで出力せよ。 各テストケースについて、条件を全て満たす $ G $ 上の trail $ (v_1,v_2,\ldots,v_k) $ を以下の形式で出力せよ。 > $ k $ $ v_1 $ $ v_2 $ $ \ldots $ $ v_k $ 条件を全て満たす $ G $ 上の trail が複数存在する場合、どれを出力しても正答となる。

### Sample Explanation 1 $ 1 $ 番目のテストケースについて考えます。 $ (v_1,v_2,v_3)=(1,3,2) $ に対し、 - $ |v_1-v_3|=|1-2|=1 $ - $ \displaystyle \frac{(N-2)^2}2=\frac12\le 3 $ - 「頂点 $ 1 $ と頂点 $ 3 $ を結ぶ辺」と「頂点 $ 3 $ と頂点 $ 2 $ を結ぶ辺」は異なる より出力例は条件を全て満たしている trail であることが確認できます。 他にも、例えば以下のような出力も正答となります。 ``` 4 2 3 1 2 ``` ### Constraints - $ 1\le T\le 50 $ - $ 3\le N\le 1000 $ - 全てのテストケースにおける $ N $ の総和は $ 1000 $ 以下 - 入力される値は全て整数