[构造]Build Permutation Codeforces1713C

A 00-indexed array aa of size nn is called good if for all valid indices ii (0≤i≤n−10≤i≤n−1), ai+iai+i is a perfect square††.

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

†† An integer xx is said to be a perfect square if there exists an integer yy such that x=y2x=y2.

‡‡ An array bb is a permutation of an array aa if bb consists of the elements of aa 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 tt (1≤t≤1041≤t≤104) — the number of test cases.

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

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

Output

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

Example

input

3
3 
4
7 

output

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

题意： 需要构造一个长度为n的排列，下标从0开始，要求每个位置的ai+i是一个平方数。

分析： 观察第三个样例可以发现，构造方法就是从后往前构造，对于位置i需要找到一个不小于i的平方数k，然后填入k-i，而之前的位置就可以递增地去填了，直到填到n为止，然后接下来的过程类似，这样是一定可以构造出一个解的。

接下来说说为什么一定有解，首先不小于x的平方数一定会出现在2*x范围内，设这个平方数为k，那对于每个位置的k-i都小于等于i，所以k-i一定在n的范围内，然后考虑是否会填入之前填过的数字，分析第三个样例:

i   : 0 1 2 3 4 5 6
a[i]: 1 0 2 6 5 4 3

i等于6时可以直接把a[3]~a[6]都填完，之后i等于2，这时候的k-i是否一定小于3呢，实际上这是一定的，因为要比较的其实就是k-i是否小于i+1（仔细观察），而k-i已知是小于等于i的，所以这就证明了不会填入之前已经填过的数字，保证答案是一个排列。

具体代码如下：

#include 
#include 
#include 
#include 
#include 
#include 
#define int long long
using namespace std;
 
int ans[100005];
 
signed main()
{
	int T;
	cin >> T;
	while(T--){
		int n;
		scanf("%lld", &n);
		int last = n; 
		int t = ceil(sqrt(n-1));
		t *= t;
		int last2 = t-(n-1);
		ans[n-1] = t-(n-1);
		for(int i = n-2; i >= 0; i--){
			if(ans[i+1]+1 < last)
				ans[i] = ans[i+1]+1;
			else{
				t = ceil(sqrt(i));
				t *= t;
				ans[i] = t-i;
				last = last2;
				last2 = t-i;
			}
		}
		for(int i = 0; i < n; i++)
			printf("%lld ", ans[i]);
		puts("");
	}
	return 0;
}