Background

This is a homework problem assigned after the backtracking and branch-and-bound sections of an Algorithm Design and Analysis course. Xiao P could not solve it and asked Xiao T for help. Xiao T solved it instantly and significantly reduced the time complexity. To prove that you are better than Xiao T, you need to solve it as well.

Simplified problem statement:

Given a positive integer $n$, partition the set $\{1, 2, 3, \dots, n\}$ into several subsets $S_1, S_2, \dots, S_k$. You must ensure that if $x$ is assigned to a subset $S_i$, then $|S_i|$ must divide $x$. Additionally, you must minimize the number of subsets that contain exactly one element. If there are multiple valid partitions, any one of them is acceptable.

Input

The input contains multiple test cases.

The first line contains an integer $T$, representing the number of test cases. Each test case follows.

For each test case, input a single line containing a positive integer $n$.

Output

For each test case:

Output a single line containing $n$ positive integers $s_1, s_2, \dots, s_n$, where $s_i$ represents the index of the subset that the number $i$ is assigned to.

Examples

Input 1

1
3

Output 1

1 2 3

Subtasks

For all test cases, it is guaranteed that $1 \le T \le 10^4$, $1 \le n \le 10^5$, and $1 \le \sum n \le 10^5$.

Note

Everyone is welcome to enroll in the Algorithm Design and Analysis (Experimental Class) offered by the School of Electronics Engineering and Computer Science at Peking University. You can learn many useful algorithmic concepts in this course, course code 04833060.