## GUPTA MECHANICAL

IN THIS WEBSITE I CAN TELL ALL ABOUT TECH. TIPS AND TRICKS APP REVIEWS AND UNBOXINGS ALSO TECH. NEWS .............

# [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,\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 ${p}_{1},{p}_{2},\dots ,{p}_{n}$, he wants to maximize the value

$\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\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\le n\le 1\phantom{\rule{thinmathspace}{0ex}}000$) — the size of the set.

Output

For each test case print a single line containing $n$ distinct integers ${p}_{1},{p}_{2},\dots ,{p}_{n}$ ($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 $\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\left\{|4-2|,|1-4|,|3-1|\right\}=min\left\{2,3,2\right\}=2$. It's easy to prove that this answer is optimal.

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