Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

The problem statement has recently been changed. View the changes.

×
C. Build Permutation

time limit per test

1 secondmemory limit per test

256 megabytesinput

standard inputoutput

standard outputA $$$\mathbf{0}$$$-indexed array $$$a$$$ of size $$$n$$$ is called good if for all valid indices $$$i$$$ ($$$0 \le i \le n-1$$$), $$$a_i + i$$$ is a perfect square$$$^\dagger$$$.

Given an integer $$$n$$$. Find a permutation$$$^\ddagger$$$ $$$p$$$ of $$$[0,1,2,\ldots,n-1]$$$ that is good or determine that no such permutation exists.

$$$^\dagger$$$ An integer $$$x$$$ is said to be a perfect square if there exists an integer $$$y$$$ such that $$$x = y^2$$$.

$$$^\ddagger$$$ 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]$$$ is a permutation of $$$[3,2,4,4]$$$ while $$$[1,2,2]$$$ is not a permutation of $$$[1,2,3]$$$.

Input

The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.

The only line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 10^5$$$) — the length of the permutation $$$p$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^5$$$.

Output

For each test case, output $$$n$$$ distinct integers $$$p_0, p_1, \dots, p_{n-1}$$$ ($$$0 \le p_i \le n-1$$$) — the permutation $$$p$$$ — if the answer exists, and $$$-1$$$ otherwise.

Example

Input

3347

Output

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

Note

In the first test case, we have $$$n=3$$$. The array $$$p = [1, 0, 2]$$$ is good since $$$1 + 0 = 1^2$$$, $$$0 + 1 = 1^2$$$, and $$$2 + 2 = 2^2$$$

In the second test case, we have $$$n=4$$$. The array $$$p = [0, 3, 2, 1]$$$ is good since $$$0 + 0 = 0^2$$$, $$$3 + 1 = 2^2$$$, $$$2+2 = 2^2$$$, and $$$1+3 = 2^2$$$.

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Feb/07/2023 21:42:47 (g1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|