[Solution] Build Permutation Codeforces Solution

Build Permutation

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

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

Given an integer n$n$. Find a permutation‡${}^{‡}$ p$p$ of [0,1,2,…,n−1]$[0,1,2,\dots ,n-1]$ that is good or determine that no such permutation exists.

†${}^{†}$ An integer x$x$ is said to be a perfect square if there exists an integer y$y$ such that x=y2$x=y^2$.

‡${}^{‡}$ An array b$b$ is a permutation of an array a$a$ if b$b$ consists of the elements of a$a$ in arbitrary order. For example, [4,2,3,4]$[4,2,3,4]$ is a permutation

Solution Click Below:-  👉CLICK HERE👈

👇👇👇👇👇

 occupied

 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$t$ (1≤t≤104$1\le t\le {10}^4$) — the number of test cases.

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

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

Output

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