[Solution] Kevin and Permutation Codeforces Solution

B. Kevin and Permutation

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

For his birthday, Kevin received the set of pairwise distinct numbers 1,2,3,…,𝑛$1,2,3,\dots ,n$ as a gift.

He is going to arrange these numbers in a way such that the minimum absolute difference between two consecutive numbers be maximum possible. More formally, if he arranges numbers in order 𝑝1,𝑝2,…,𝑝𝑛$p_1,p_2,\dots ,p_n$, he wants to maximize the value

min𝑖=1𝑛−1|𝑝𝑖+1−𝑝𝑖|,$$\underset{i=1}{\overset{n-1}{min}}|p_{i+1}-p_i|,$$

where |𝑥|$|x|$ denotes the absolute value of 𝑥$x$.

Help Kevin to do that.

Input

Each test consists of multiple test cases. The first line contains a single integer 𝑡$t$ (1≤𝑡≤100$1\le t\le 100$) — the number of test cases. Description of the test cases follows.

The only line of each test case contains an integer 𝑛$n$ (2≤𝑛≤1000$2\le n\le 1000$) — the size of the set.

Output

For each test case print a single line containing 𝑛$n$ distinct integers 𝑝1,𝑝2,…,𝑝𝑛$p_1,p_2,\dots ,p_n$ (1≤𝑝𝑖≤𝑛$1\le p_i\le n$) describing the arrangement that maximizes the minimum absolute difference of consecutive elements.

Formally, you have to print a permutation 𝑝$p$ which maximizes the value min𝑖=1𝑛−1|𝑝𝑖+1−𝑝𝑖|$\underset{i=1}{\overset{n-1}{min}}|p_{i+1}-p_i|$.

If there are multiple optimal solutions, print any of them.

Note

In the first test case the minimum absolute difference of consecutive elements equals min{|4−2|,|1−4|,|3−1|}=min{2,3,2}=2$min\{|4-2|,|1-4|,|3-1|\}=min\{2,3,2\}=2$. It's easy to prove that this answer is optimal.

In the second test case each permutation of numbers 1,2,3$1,2,3$ is an optimal answer. The minimum absolute difference of consecutive elements equals to 1