# [Solution] Build Permutation solution codeforces

Build Permutation solution codeforces – A 00-indexed array 𝑎a of size 𝑛n is called good if for all valid indices 𝑖i (0𝑖𝑛10≤i≤n−1), 𝑎𝑖+𝑖ai+i is a perfect square.

## [Solution] Build Permutation solution codeforces

Given an integer 𝑛n. Find a permutation 𝑝p of [0,1,2,,𝑛1][0,1,2,…,n−1] that is good or determine that no such permutation exists.

An integer 𝑥x is said to be a perfect square if there exists an integer 𝑦y such that 𝑥=𝑦2x=y2.

An array 𝑏b is a permutation of an array 𝑎a if 𝑏b consists of the elements of 𝑎a in arbitrary order. For example, [4,2,3,4][4,2,3,4] is a permutation of [3,2,4,4][3,2,4,4] while [1,2,2][1,2,2] is not a permutation of [1,2,3][1,2,3].

Input

The first line contains a single integer 𝑡t (1𝑡1041≤t≤104) — the number of test cases.

The only line of each test case contains a single integer 𝑛n (1𝑛1051≤n≤105) — the length of the permutation 𝑝p.

It is guaranteed that the sum of 𝑛n over all test cases does not exceed 105105.

## [Solution] Build Permutation solution codeforces

For each test case, output 𝑛n distinct integers 𝑝0,𝑝1,,𝑝𝑛1p0,p1,…,pn−1 (0𝑝𝑖𝑛10≤pi≤n−1) — the permutation 𝑝p — if the answer exists, and 1−1 otherwise.

Example
input

Copy
3
3
4
7

output

Copy
1 0 2
0 3 2 1
1 0 2 6 5 4 3


## [Solution] Build Permutation solution codeforces

In the first test case, we have 𝑛=3n=3. The array 𝑝=[1,0,2]p=[1,0,2] is good since 1+0=121+0=120+1=120+1=12, and 2+2=222+2=22

In the second test case, we have 𝑛=4n=4. The array 𝑝=[0,3,2,1]p=[0,3,2,1] is good since 0+0=020+0=023+1=223+1=222+2=222+2=22, and 1+3=221+3=22.