At the Sumeru Akademiya, scholars have a long-standing tradition of exchanging academic ideas at the round tables in the House of Daena. Seeing this, Nahida decided to host a weekly "Round Table Conference" and entrusted the seating arrangements for the scholars entirely to the Wanderer.

There are $n$ scholars in Sumeru, each with different abilities and research interests, which can be perfectly represented by a permutation of $1$ to $n$ denoting their ability values. The round table conference uses circular seating, where each scholar forms a "discussion group" with the two companions sitting immediately to their left and right. Throughout the entire conference, a total of $n$ such groups are formed. The discussion topic for each group is led by the scholar with the median ability value among the three, so the topic ID of the group is exactly the median of the three ability values. Nahida does not want the discussion content to be too scattered, so she requires the number of distinct topic IDs to be as small as possible. This difficult problem now lies before the Wanderer, but he has not been able to find a good solution, so he has come to you. Can you help him find a suitable seating arrangement?

Input

Each test file contains multiple test cases.

The first line contains an integer $T$ ($1 \le T \le 10^5$) representing the number of test cases. For each test case:

The only line contains an integer $n$ ($4 \le n \le 10^6$), representing the number of scholars.

It is guaranteed that the sum of $n$ over all test cases in a single test file does not exceed $10^6$.

Output

For each test case, output a single line containing $n$ integers, which is a permutation of $1$ to $n$, representing the seating arrangement of the scholars.

If there are multiple possible answers, you may output any one of them.

Examples

Input 1

2
4
5

Output 1

1 2 3 4
1 2 3 4 5