AT_arc220_d [ARC220D] Long Trail

You are given a positive integer $ N $ . Let $ G $ be a complete undirected graph with $ N $ vertices $ 1,2,\ldots,N $ and $ \displaystyle \frac{N(N-1)}2 $ edges. Find a trail $ (v_1,v_2,\ldots,v_k) $ on $ G $ satisfying all of the following conditions. - for all integers $ i $ such that $ 1 \leq i \leq k-2 $ , $ |v_i - v_{i+2}| = 1 $ - $ \displaystyle \frac{(N-2)^2}2 \le k $ It can be proved that such a trail always exists under the constraints. What is a trail? A sequence of vertices $ (v_1,v_2,\ldots,v_k) $ on an undirected graph $ G $ is called a trail on $ G $ if all of the following conditions are satisfied. - $ 1\le v_i\le N. $ - For $ 1\le i\le k-1 $ , there exists an edge connecting vertices $ v_i $ and $ v_{i+1} $ . - For $ 1\le i < j \le k-1 $ , the edge connecting vertices $ v_i $ and $ v_{i+1} $ and the edge connecting vertices $ v_j $ and $ v_{j+1} $ are distinct.

The input is given from Standard Input in the following format: > $ T $ $ \text{case}_1 $ $ \text{case}_2 $ $ \vdots $ $ \text{case}_T $ Each test case is given in the following format: > $ N $

Output the answers for the test cases in order, separated by newlines. For each test case, output a trail $ (v_1,v_2,\ldots,v_k) $ on $ G $ satisfying all conditions in the following format: > $ k $ $ v_1 $ $ v_2 $ $ \ldots $ $ v_k $ If multiple trails on $ G $ satisfying all conditions exist, any of them will be accepted.

### Sample Explanation 1 Consider the first test case. For $ (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 $ - The edge connecting vertices $ 1 $ and $ 3 $ and the edge connecting vertices $ 3 $ and $ 2 $ are distinct. Thus, we can confirm that the sample output is a trail satisfying all conditions. The following output, for example, is also accepted: ``` 4 2 3 1 2 ``` ### Constraints - $ 1\le T\le 50 $ - $ 3\le N\le 1000 $ - The sum of $ N $ over all test cases is at most $ 1000 $ . - All input values are integers.