A $\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.


-----Examples-----

Input
3
3
4
7
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$.

Source: codeforces | Difficulty: EASY
Tags: Dynamic programming

Mathematics

Constructive algorithms


Solutions:
import sys
input = sys.stdin.readline

def solution(n):
	current = n - 1
	r = int(current ** 0.5)
	if r ** 2 < current:
		r += 1
	first = r ** 2 - current
	if first == 0:
		return list(range(n))
	return list(range(first, n)) + solution(first)
t = int(input())
for _ in range(t):
	n = int(input())
	result = solution(n)
	print(' '.join(map(str, result[::-1])))


import sys, math
INPUT = sys.stdin.readline

def ii():
	return int(INPUT())

def iit(strip=False):
	s = INPUT().strip('[]\n').split(',') if strip else INPUT().split()
	return map(int, s)

def iil(strip=False):
	s = INPUT().strip('[]\n').split(',') if strip else INPUT().split()
	return list(map(int, s))

def si():
	return INPUT()[:-1]

def rec(n):
	m = n - 1
	ma = int(math.sqrt(m))
	if ma ** 2 == m:
		return list(reversed(range(n)))
	mb = ma + 1
	nn = mb ** 2 - m
	return rec(nn) + list(reversed(range(nn, n)))

def solve():
	n = ii()
	r = rec(n)
	print(' '.join([str(x) for x in r]))
CASES = True
FROM_FILE = False
if FROM_FILE:
	FILE = open('input.txt', 'r')
	INPUT = FILE.readline
if CASES:
	t = ii()
	for i in range(t):
		solve()
else:
	solve()
if FROM_FILE:
	FILE.close()


squares = [x ** 2 for x in range(1000)]

def find_border(x):
	index = 0
	while x > squares[index]:
		index += 1
	return squares[index]
t = int(input())
for i in range(t):
	n = int(input())
	lst = []
	current = n - 1
	while current >= 0:
		border = find_border(current)
		lst.extend(list(range(border - current, current + 1)))
		current = border - current - 1
	print(' '.join(map(str, reversed(lst))))


import bisect

def main():
	t = int(input())
	mem = [i ** 2 for i in range(449)]
	while t:
		t -= 1
		n = int(input())
		output = [0] * n
		max_el = n - 1
		curr_n = n
		while max_el > 0:
			indx = bisect.bisect_left(mem, max_el)
			if mem[indx] == max_el:
				put_idx = 0
			else:
				put_idx = mem[indx] - max_el
			for i in range(put_idx, curr_n):
				output[i] = curr_n - (i - put_idx + 1)
			curr_n = put_idx
			max_el = curr_n - 1
		print(' '.join(map(str, output)))
main()


import math as m

def div(n):
	if n == 0 or n == 1:
		return [0]
	if n == 2:
		return [1, 0]
	if n == 5:
		return list(range(4, -1, -1))
	q = m.ceil(m.sqrt(n)) ** 2
	return div(q - n + 1) + list(range(n - 1, q - n, -1))
c = int(input())
while c:
	n = int(input())
	print(' '.join((str(i) for i in div(n))))
	c -= 1


import math

def solve(n):
	if n == 1:
		return [0]
	if n == 2:
		return [1, 0]
	if n == 3:
		return [1, 0, 2]
	q = int(math.ceil((n - 1) ** 0.5))
	Q = q * q
	k = Q - (n - 1)
	if k > 0:
		return solve(k) + [i for i in range(n - 1, k - 1, -1)]
	else:
		return [i for i in range(n - 1, k - 1, -1)]

def main():
	n = int(input())
	for _ in range(n):
		n = int(input())
		print(' '.join([str(x) for x in solve(n)]))
		pass
	pass
main()


import math

def solve():
	n = int(input())
	ls = []
	curr = math.ceil(math.sqrt(n - 1)) ** 2 - n + 1
	i = n - 1
	while curr >= 0:
		temp = []
		while i >= curr:
			temp.append(i)
			i -= 1
		ls = temp + ls
		if curr >= 1:
			curr = math.ceil(math.sqrt(curr - 1)) ** 2 - curr + 1
		else:
			break
	print(' '.join(map(str, ls)))
t = int(input())
for _ in range(t):
	solve()


from math import ceil, sqrt

def rec(n):
	square = ceil(sqrt(n - 1)) ** 2
	num = n - (square - (n - 1))
	s = ''
	n -= 1
	for i in range(num):
		s += str(n) + ' '
		n -= 1
	return (s, n + 1)
iter = int(input())
for z in range(iter):
	n = int(input())
	ans = ''
	while n:
		(tp, n) = rec(n)
		ans = tp + ans
	print(ans)


from math import floor, sqrt
t = int(input())
sol = []

def solve(n):
	if n == 0:
		return []
	if n == 1:
		return [0]
	if n == 2:
		return [1, 0]
	n -= 1
	if floor(sqrt(n)) ** 2 == n:
		square = n
	else:
		square = (floor(sqrt(n)) + 1) ** 2
	if square > 2 * n:
		return -1
	if square - n < 0:
		return -1
	sol = []
	for i in range(square - n, n + 1):
		sol.append(square - i)
	rest = solve(square - n)
	if rest == -1:
		return -1
	return rest + sol
	return
for _ in range(t):
	sol.append(solve(int(input())))
for s in sol:
	if s == -1:
		print(-1)
	else:
		print(' '.join([str(x) for x in s]))


def find(n, answer):
	i = 0
	while i * i < n:
		i += 1
	start = i * i - n
	for x in range(start, n + 1):
		answer[x] = i * i - x
	if start == 0:
		return answer
	else:
		return find(start - 1, answer)

def solve():
	n = int(input())
	answer = {}
	find(n - 1, answer)
	print(' '.join((str(answer[i]) for i in range(n))))
T = int(input())
for _ in range(T):
	solve()


def sqt(n):
	ind = 0
	while ind * ind <= 2 * n - 2:
		ind += 1
	return ind - 1

def cf(n):
	occ = [-1 for i in range(n)]
	end = n
	ind = sqt(n)
	ink = ind * ind - (n - 1)
	store = ink
	i = n - 1
	while i >= 0:
		if ink < end:
			occ[i] = ink
			ink += 1
			i -= 1
		else:
			ind -= 1
			ink = ind * ind - i
			end = store
			store = min(ink, store)
	return occ
t = int(input())
for i in range(t):
	n = int(input())
	s = ' '.join(map(str, cf(n)))
	print(s)


for _ in range(int(input())):
	n = int(input())
	array = [0] * n
	p = n - 1
	while p >= 0:
		m = 0
		while m * m < p:
			m += 1
		d = m * m - p
		for idx in range(d, p + 1):
			array[idx] = p + d - idx
		p = d - 1
	print(' '.join(map(str, array)))


t = int(input())
for tries in range(t):
	n = int(input())

	def pi(n):
		if n > 1:
			if int(n ** 0.5) ** 2 == n:
				return '0 ' + ' '.join([str(x) for x in range(n - 1, 0, -1)])
			elif int((n - 1) ** 0.5) ** 2 == n - 1:
				return ' '.join([str(x) for x in range(n - 1, -1, -1)])
			else:
				sqr = (int(n ** 0.5) + 1) ** 2
				ans = pi(sqr - n + 1) + ' ' + ' '.join([str(x) for x in range(n - 1, sqr - n, -1)])
				return ans
		else:
			return '0 '
	print(pi(n))


import math
for _ in range(int(input())):
	n = int(input())
	r = ''
	k = math.floor(math.sqrt(2 * (n - 1)))
	while k > 1:
		r1 = ''
		for i in range(n - 1, k * k - n, -1):
			r1 = r1 + str(i) + ' '
		n = k * k - n + 1
		r = r1 + r
		if n < 3:
			break
		else:
			k = math.floor(math.sqrt(2 * (n - 1)))
	if n == 2:
		r = '1 0 ' + r
	elif n == 1:
		r = '0 ' + r
	print(r)


import math

def nextsqr(x):
	sqr = math.floor(math.sqrt(x))
	if sqr * sqr == x:
		return x
	return (sqr + 1) ** 2

def solve(x):
	if x < 0:
		return []
	if x == 0:
		return [0]
	if x == 1:
		return [1, 0]
	sq = nextsqr(x)
	if sq - x > x:
		print('??', sq, x)
		return None
	y = sq - x
	re = solve(y - 1)
	if re is None:
		return None
	z = [sq - z for z in range(y, x + 1)]
	return re + z
t = int(input())
for i in range(t):
	n = int(input())
	out = solve(n - 1)
	if out is None:
		print(-1)
	else:
		print(' '.join([str(x) for x in out]))


from math import ceil
for _ in range(int(input())):
	n = int(input())
	or_n = n
	biggest_square = ceil((n - 1) ** 0.5) ** 2
	out = []
	used_min = biggest_square - n + 1
	while n >= 0:
		for x in range(used_min, biggest_square - used_min + 1):
			n -= 1
			out.append(x)
		if n == 0:
			break
		biggest_square = ceil((n - 1) ** 0.5) ** 2
		used_min = biggest_square - n
		used_min += 1
		if biggest_square == 0:
			break
	if 0 not in out:
		out.append(0)
	print(' '.join((str(x) for x in out[::-1])))


from math import sqrt, ceil, inf

def solve(n):
	perm = [0] * n

	def least_above_sq(q):
		return ceil(sqrt(q)) ** 2
	star = least_above_sq(len(perm) - 1)
	used = set()
	for k in range(len(perm) - 1, -1, -1):
		if star - k >= len(perm) or star - k in used:
			star = least_above_sq(k)
		used.add(star - k)
		perm[k] = star - k
	return ' '.join((str(c) for c in perm))
t = int(input())
for _ in range(t):
	n = int(input())
	print(solve(n))


t = int(input())
square_nums = [a * a for a in range(1000)]
noless_squares_nums_dict = {0: 0, 1: 1}
idx = 2
for i in range(2, 100000 + 5):
	if i > square_nums[idx]:
		idx += 1
	noless_squares_nums_dict[i] = square_nums[idx]
for _ in range(t):
	n = int(input())
	permuatation = [-1] * n
	concerned_num = n - 1
	while True:
		if concerned_num <= 0:
			for i in range(concerned_num + 1):
				permuatation[i] = i
			break
		pair_num = noless_squares_nums_dict[concerned_num] - concerned_num
		for i in range(concerned_num - pair_num + 1):
			permuatation[pair_num + i] = concerned_num - i
		concerned_num = pair_num - 1
	print(' '.join([str(i) for i in permuatation]))


t = int(input())
while t:
	t -= 1
	n = int(input())
	arr = [i for i in range(n)]
	ans = [-1 for i in range(n)]
	last_done = n - 1
	while last_done > -1:
		x = int(last_done ** 0.5)
		while x * x < last_done:
			x += 1
		num_to_make = x * x
		start = x * x - last_done
		for i in range(start, last_done + 1):
			ans[i] = last_done
			last_done -= 1
		print
	ans = list(map(str, ans))
	print(' '.join(ans))


import functools
xx = int(input())

@functools.lru_cache(None)
def cal(n):
	if n == 1:
		return [0]
	if n == 2:
		return [1, 0]
	if n == 3:
		return [1, 0, 2]
	p = int((n - 1) ** 0.5)
	if p * p == n - 1:
		return list(range(n))[::-1]
	k = (p + 1) ** 2 - n + 1
	return cal(k) + list(range(k, n))[::-1]
for jj in range(xx):
	n = int(input())
	t = cal(n)
	print(' '.join([str(i) for i in t]))


MemLis = [None] * 100001

def MS(n):
	if not MemLis[n]:
		MemLis[n] = MemorySearch(n)
	return MemLis[n]

def MemorySearch(n: int):
	square = int(n ** 0.5)
	if n == square ** 2:
		return [0] + list(range(n - 1, 0, -1))
	if n == square ** 2 + 1:
		return list(range(n - 1, -1, -1))
	key = (square + 1) ** 2 - n + 1
	return MS(key) + list(range(n - 1, key - 1, -1))
for _ in range(int(input())):
	print(*MemorySearch(int(input())))


import math
for _ in range(int(input())):
	l = int(input()) - 1
	nearest_square = lambda x: int(math.sqrt(x) + 1) ** 2
	perms = [l]
	while math.sqrt(l) != int(math.sqrt(l)):
		l = nearest_square(l) - l - 1
		perms.append(l)
	perms.append(-1)
	lis = []
	perms = list(reversed(perms))
	for x in range(1, len(perms)):
		lis = lis + list(reversed(list(range(perms[x - 1] + 1, perms[x] + 1))))
	print(' '.join([str(x) for x in lis]))


t = int(input())
for case in range(t):
	n = int(input())
	largest_square = (2 * n) ** 0.5 // 1
	if (2 * n) ** 0.5 % 1 == 0:
		largest_square -= 1
	min_val = n
	current = largest_square ** 2 - (n - 1)
	started = current
	out = []
	i = n - 1
	while i >= 0:
		if current >= min_val:
			min_val = started
			while current >= started:
				current -= 2 * largest_square - 1
				largest_square -= 1
			started = current
		out.append(str(int(current)))
		current += 1
		i -= 1
	print(' '.join(out[::-1]))


from itertools import permutations
import math

def find_good0(n, debug=False):
	for p in permutations(range(0, int(n))):
		if all((math.sqrt(a + i) % 1 == 0 for (a, i) in enumerate(p))):
			if debug:
				print(' '.join(map(str, p)))
			if debug:
				print(' '.join(map(str, [math.sqrt(n + i) for (n, i) in enumerate(p)])))
			return p
	return -1

def find_good(n):
	original = range(n)
	new = [None for _ in original]
	upper_root = math.floor(math.sqrt(2 * (n - 1)))
	for i in range(len(original) - 1, -1, -1):
		pos = None
		extra = 0
		while True:
			root = upper_root - extra
			if root < 0:
				return -1
			pos = root ** 2 - original[i]
			if pos < len(new) and new[pos] == None:
				new[pos] = original[i]
				break
			extra += 1
		upper_root -= extra
	return new
for _ in range(int(input())):
	n = int(input())
	print(' '.join(map(str, find_good(n))))


import math
q = int(input())
for _ in range(q):
	n = int(input())
	l = list(range(0, n))
	i = n - 1
	while i > 0:
		k = math.ceil(math.sqrt(i)) ** 2 - l[i]
		if k == 0:
			l = l[:i + 1][::-1] + l[i + 1:]
			break
		elif k == 1:
			l = [l[0]] + l[1:i + 1][::-1] + l[i + 1:]
			break
		elif k == 2:
			l = [1, 0] + l[2:i + 1][::-1] + l[i + 1:]
			break
		else:
			l = l[:k] + l[k:i + 1][::-1] + l[i + 1:]
			i = k - 1
			continue
	print(*l)


import sys
n = int(input())
ans = []
for _ in range(n):
	n = int(input())
	a = [0] * n
	p = n - 1
	while p >= 0:
		i = 0
		while i * i < p:
			i += 1
		l = i * i - p
		for k in range(l, p + 1):
			a[k] = p + l - k
		p = l - 1
	ans.append(a)
for i in ans:
	print(*i)


import sys
num = int(input())
answer = []
for _ in range(num):
	num = int(input())
	a = [0] * num
	p = num - 1
	while p >= 0:
		i = 0
		while i * i < p:
			i += 1
		l = i * i - p
		for k in range(l, p + 1):
			a[k] = p + l - k
		p = l - 1
	answer.append(a)
for i in answer:
	print(*i)


I = input
(R, G) = (lambda : int(I()), range)

def f(k):
	if k < 0:
		return
	s = int((2 * k) ** 0.5)
	s *= s
	l = s - k
	f(l - 1)
	while l <= k:
		z[l] = k
		z[k] = l
		l += 1
		k -= 1
for _ in G(R()):
	n = R()
	z = [0] * n
	f(n - 1)
	print(*z)


t = int(input())
for i in range(t):
	n = int(input()) - 1
	ans = []
	while n >= 0:
		k = int((2 * n) ** (1 / 2)) ** 2
		ans = list(reversed(range(k - n, n + 1))) + ans
		n = k - n - 1
	print(*ans)


t = int(input())
for rep in range(t):
	n = int(input())
	if n == 1:
		print(0)
		continue
	sq = 1
	while sq ** 2 < n - 1:
		sq += 1
	if sq ** 2 - (n - 1) > n - 1:
		print(-1)
		continue
	ans = [-1 for x in range(n)]
	mn = sq ** 2 - (n - 1)
	mx = n - 1
	ans[-1] = mn
	for x in range(n - 2, -1, -1):
		if sq ** 2 - x > mx:
			while sq ** 2 - x >= mn:
				sq -= 1
				if sq < 0:
					break
			if sq < 0:
				break
			(mx, mn) = (mn - 1, sq ** 2 - x)
		ans[x] = sq ** 2 - x
	if -1 in ans:
		print(-1)
		continue
	print(' '.join([str(i) for i in ans]))


import math
for t in range(int(input())):
	n = int(input())
	t = n - 1
	rslt = [0] * n
	ns = math.ceil(math.sqrt(t)) ** 2
	if n ** 0.5 != ns:
		while True:
			ns = math.ceil(math.sqrt(t)) ** 2
			for i in range(ns - t, t + 1):
				rslt[i] = ns - i
			t = ns - t - 1
			if t < 0:
				break
		print(*rslt)
	else:
		print(*[x for x in range(t, -1, -1)])


import math

def calc(x):
	if x >= 0:
		res = math.ceil(x ** 0.5) ** 2 - x
		calc(res - 1)
		for i in range(x, res - 1, -1):
			print(i, end=' ')
T = int(input())
while T > 0:
	n = int(input())
	if n == 0:
		print(0, end='\n')
		continue
	calc(n - 1)
	print(end='\n')
	T -= 1


for _ in range(int(input())):
	n = int(input())
	a = [0] * n
	p = n - 1
	while p >= 0:
		i = 0
		while i * i < p:
			i = i + 1
		x = i * i - p
		for k in range(x, p + 1):
			a[k] = p + x - k
		p = x - 1
	print(*a)


import sys
import math
input = sys.stdin.readline

def find_permutation(arr, n):
	if arr[n] != math.inf:
		return arr[n]
	else:
		check = math.floor(math.sqrt((n - 1) * 2))
		return find_permutation(arr, check ** 2 - (n - 1)) + list(range(n - 1, check ** 2 - (n - 1) - 1, -1))
dp = [math.inf for _ in range(10 ** 5 + 1)]
dp[0] = []
dp[1] = [0]
dp[2] = [1, 0]
for _ in range(int(input())):
	n = int(input())
	answer = find_permutation(dp, n)
	for num in answer:
		print(num, end=' ')
	print()


import math

def solve(n):
	x = math.sqrt(n)
	if int(x) == x:
		for i in range(n, -1, -1):
			print(i, end=' ')
	else:
		y = math.ceil(x)
		y = y * y - n
		solve(y - 1)
		for j in range(n, y - 1, -1):
			print(j, end=' ')
for _ in range(int(input())):
	n = int(input())
	solve(n - 1)
	print()


import math
for _ in range(int(input())):
	t = int(input())
	a = [0] * t
	curr = t - 1
	while curr >= 0:
		rem = math.ceil(math.sqrt(curr)) ** 2
		for x in range(rem - curr, curr + 1):
			a[x] = rem - x
		curr = rem - curr - 1
	print(*a)


import math
for i in range(int(input())):
	a = int(input())
	index = a - 1
	point = a - 1
	li = [0] * a
	while index > 0:
		x = pow(math.ceil(math.sqrt(index)), 2) - index
		for i in range(index + 1 - x):
			li[i + x] = point
			point -= 1
		index = x - 1
	print(*li)


from math import ceil

def issquare(n):
	return int(n ** 0.5) == n ** 0.5

def good(n):
	if n == 1:
		return [0]
	elif n == 2:
		return [1, 0]
	if issquare(n - 1):
		return list(range(n - 1, -1, -1))
	ns = ceil(n ** 0.5) ** 2
	diff = ns - n + 1
	return good(diff) + list(range(n - 1, diff - 1, -1))
for _ in range(int(input())):
	print(*good(int(input())), sep=' ')


from array import array
import collections
import sys
input = sys.stdin.readline

def inp():
	return int(input())

def inlt():
	return list(map(int, input().split()))

def insr():
	s = input()
	return list(s[:len(s) - 1])

def invr():
	return map(int, input().split())
for _ in range(inp()):
	n = inp()

	def solve(n: int):
		squares = []
		num = 0
		while num * num <= 2 * (n - 1):
			squares.append(num * num)
			num += 1
		ans = [0 for _ in range(n)]
		used = set()
		for i in range(n - 1, -1, -1):
			if not squares:
				break
			while squares[-1] - i in used or squares[-1] - i >= n:
				squares.pop()
			v = squares[-1] - i
			ans[i] = v
			used.add(v)
		return ans
	ans = solve(n)
	print(*ans)


def solve(n, A):
	if n < 0:
		return
	a = int((2 * n) ** 0.5)
	a = a * a
	b = a - n
	solve(b - 1, A)
	while b <= n:
		A[b] = n
		A[n] = b
		b += 1
		n -= 1
t = int(input())
for _ in range(t):
	n = int(input())
	A = [0] * n
	solve(n - 1, A)
	print(*A)


from math import sqrt, ceil
import sys
sys.setrecursionlimit(10 ** 8)

def function(end):
	if end < 0:
		return []
	if end == 0:
		return [0]
	temp = int(ceil(sqrt(end)))
	return function(temp * temp - end - 1) + [x for x in range(end, temp * temp - end - 1, -1)]
t = int(input())
for _ in range(t):
	m = int(input())
	arr = function(m - 1)
	for i in arr:
		print(i, end=' ')
	print()


import math

def solve(r):
	if r < 0:
		return
	s = int(math.sqrt(2 * r))
	s *= s
	l = s - r
	solve(l - 1)
	while l <= r:
		ans[l] = r
		ans[r] = l
		l += 1
		r -= 1
for _ in range(int(input())):
	n = int(input())
	ans = [0] * n
	solve(n - 1)
	print(*ans, end=' ')
	print()


def f(n):
	if n == 1:
		p = []
		p.append(0)
		return p
	if n == 2:
		p = []
		p.append(1)
		p.append(0)
		return p
	if n == 3:
		p = []
		p.append(1)
		p.append(0)
		p.append(2)
		return p
	if n == 4:
		p = []
		p.append(0)
		p.append(3)
		p.append(2)
		p.append(1)
		return p
	if n == 5:
		p = []
		p.append(4)
		p.append(3)
		p.append(2)
		p.append(1)
		p.append(0)
		return p
	maxim = n - 1
	if int(maxim ** 0.5) ** 2 == maxim:
		y = int(maxim ** 0.5)
	y = int(maxim ** 0.5 + 1)
	y *= y
	mas = []
	for i in range(n - 1, y - maxim - 1, -1):
		mas.append(i)
	g = []
	g = f(y - maxim)
	for i in range(len(mas)):
		g.append(mas[i])
	return g
t = int(input())
while t:
	t -= 1
	n = int(input())
	print(*f(n))


cas = int(input())
for j in range(cas):
	n = int(input())
	a = [0] * n
	p = n - 1
	while p >= 0:
		i = 0
		while i * i < p:
			i = i + 1
		x = i * i - p
		for k in range(x, p + 1):
			a[k] = p + x - k
		p = x - 1
	print(*a)


test_case = int(input())
for ele in range(test_case):
	n = int(input())
	p = n - 1
	ans = [0] * n
	while p >= 0:
		i = 0
		while i * i < p:
			i = i + 1
		perfect_square_wanted = i * i
		start = perfect_square_wanted - p
		for j in range(start, p + 1):
			ans[j] = perfect_square_wanted - j
		p = start - 1
	print(*ans)


def isqrt(n):
	x_0 = n >> 1
	if not x_0:
		return n
	x_1 = x_0 + n // x_0 >> 1
	while x_1 < x_0:
		x_0 = x_1
		x_1 = x_0 + n // x_0 >> 1
	return x_0
t = int(input())
for _ in range(t):
	n = int(input())
	A = [0] * n
	while n > 2:
		m = isqrt(n - 1)
		m += m * m != n - 1
		x = m * m - n
		A[x + 1:n] = range(n - 1, x, -1)
		n = x + 1
	A[:n] = list(range(n))[::-1]
	print(*A)


for _ in range(int(input())):
	n = int(input())
	m = n - 1
	p = int(pow(m, 1 / 2))
	if p * p == m:
		print(*list(range(m + 1))[::-1])
		continue
	elif 2 * m + 1 < (p + 1) * (p + 1):
		print(-1)
		continue
	interval = []
	i = n - 1
	while i > 0:
		p = int(pow(i, 1 / 2))
		q = p + 1
		if p * p == i:
			interval.append((i, p * p - i))
			i = p * p - i
		elif q ** 2 > 2 * i + 1:
			print(-1)
			break
		else:
			interval.append((i, q * q - i))
			i = q * q - i - 1
	else:
		lst = interval[::-1]
		res = []
		for (x, y) in lst:
			res += list(range(x, y - 1, -1))
		if 0 not in res:
			res = [0] + res
		print(*res)


import math

def get_max_square(n):
	if n <= 0:
		return 0
	else:
		return math.ceil(math.sqrt(n)) ** 2
t = int(input())
for _ in range(t):
	n = int(input())
	max_square = get_max_square(n - 1)
	ans = []
	p = 100
	maxdex = n - 1
	while p > 0:
		p = max(0, max_square - maxdex)
		ans = [x for x in range(maxdex, p - 1, -1)] + ans
		max_square = get_max_square(p - 1)
		maxdex = p - 1
	print(*ans)


t = int(input())

def find(n, arr):
	if n == 1:
		arr[0] = 0
		return arr
	diff = (n - 1) ** 0.5 - int((n - 1) ** 0.5)
	if diff == 0.0:
		k = int(n - 1)
	else:
		k = int((n - 1) ** 0.5 + 1) ** 2
	a = k - (n - 1)
	i = n - 1
	while a < n:
		arr[i] = a
		i -= 1
		a += 1
	if i == -1:
		return arr
	else:
		find(i + 1, arr)
for j in range(t):
	n = int(input())
	arr = [0] * n
	find(n, arr)
	print(*arr)


import math
n = int(input(''))
for i in range(n):
	n2 = int(input(''))
	list_nums = list(range(n2))
	l2 = list('0' * n2)
	n3 = math.ceil((n2 - 1) ** 0.5) ** 2
	g = n2 - 1
	if n2 - 1 == n3:
		print(*list_nums[::-1], sep=' ')
	else:
		for i in range(n2 - 1, -1, -1):
			diff = n3 - i
			if diff > g:
				n3 = math.ceil(i ** 0.5) ** 2
				diff = n3 - i
				g = i
			l2[i] = diff
		print(*l2, sep=' ')


import math

def solve(n, permutation):
	if n < 0:
		return permutation
	x = math.sqrt(n)
	if x == int(x):
		for i in range(n + 1):
			permutation[i] = n - i
		return permutation
	else:
		x = int(x) + 1
		x = int(math.pow(x, 2))
		for i in range(x - n, n + 1):
			permutation[i] = n - (i - (x - n))
		return solve(x - n - 1, permutation)
for _ in range(int(input())):
	n = int(input())
	n -= 1
	permutations = [-1 for i in range(n + 1)]
	a = solve(n, permutations)
	print(*a)


from sys import stdin
rd = stdin.readline

def rec(n):
	if n <= -1:
		return
	s = int((2 * n) ** 0.5) ** 2
	l = s - n
	rec(l - 1)
	while l <= n:
		ans[l] = n
		ans[n] = l
		l += 1
		n -= 1
for _ in range(int(rd())):
	n = int(rd())
	ans = [0] * n
	rec(n - 1)
	for i in range(n):
		print(ans[i], end=' ')
	print()


import math
testCase = int(input())

def sortPerm(arr, x):
	if x < 0:
		return
	last = arr[x - 1]
	for j in range(x):
		if math.floor(math.sqrt(last + j)) == math.ceil(math.sqrt(last + j)):
			z = 0
			for k in range(j, x):
				arr[k] = last - z
				z += 1
			return sortPerm(arr, j)
for i in range(testCase):
	n = int(input())
	arr = [x for x in range(n)]
	curr = n
	sortPerm(arr, curr)
	arr = [str(x) for x in arr]
	print(' '.join(arr))


import sys
import math
input = sys.stdin.readline
from collections import defaultdict
for i in range(int(input())):
	n = int(input())
	idx = math.ceil((n - 1) ** 0.5)
	a = [-1] * n
	mnt = [0] * n
	cnt = True
	for i in range(n - 1, -1, -1):
		while idx >= 0:
			p = idx ** 2 - i
			if p < n:
				if mnt[p] == 0:
					a[i] = p
					mnt[p] = 10 ** 9
					break
			idx -= 1
		if a[i] == -1:
			print(-1)
			cnt = False
			continue
	if cnt == True:
		print(*a)


import math
from collections import *

def solve():
	n = int(input())
	ans = [0] * n
	a = []
	for i in range(1, n):
		if i ** 2 >= n - 1:
			a.append(i ** 2)
			break
		else:
			a.append(i ** 2)
	l = {}
	for i in range(len(a) - 1, -1, -1):
		d = a[i] - (n - 1)
		if d not in l:
			for i in range(d, n):
				ans[i] = n - 1
				l[ans[i]] = 1
				n -= 1
			n = d
		if n == 1:
			break
	print(*ans)
t = int(input())
for _ in range(t):
	solve()


def next_square(num):
	if num == 0:
		return 0
	a = 0
	b = num
	while b - a > 1:
		g = (a + b) // 2
		if g ** 2 == num:
			return num
		elif g ** 2 > num:
			b = g
		else:
			a = g
	return b ** 2

def make(num):
	if num == 0:
		return []
	k = next_square(num - 1)
	p = 2 * num - k - 1
	ans = make(num - p) + [i for i in range(num - 1, num - p - 1, -1)]
	return ans
testcase = int(input())
for _ in range(testcase):
	n = int(input())
	ans = make(n)
	print(*ans)


import sys
import collections
from math import ceil, gcd, sqrt, log, floor
import bisect
INF = float('inf')
mod = 1000000007

def cat(c):
	i = c
	while i * i > c:
		i -= 1
	return i * i

def solve():
	n = int(input())
	ans = [0] * n
	i = n - 1
	while i >= 0:
		for j in range(i + 1):
			p = i + j
			sq = floor(sqrt(p))
			if sq * sq == p:
				k1 = j
				k2 = i
				while k1 <= k2:
					ans[k1] = k2
					ans[k2] = k1
					k1 += 1
					k2 -= 1
				i = j - 1
				break
	print(*ans)
t = int(input())
while t != 0:
	solve()
	t -= 1


import math
for _ in range(int(input())):
	n = int(input())
	arr = []
	l = 0
	h = n - 1
	m = math.ceil(math.sqrt(n - 1))
	while m >= 0:
		l = m ** 2 - h
		for j in range(l, h + 1):
			arr.append(j)
		if l == 0:
			break
		h = l - 1
		m = math.ceil(math.sqrt(l - 1))
	arr.reverse()
	for i in arr:
		print(i, end=' ')
	print()


import math
t = int(input())
for i in range(t):
	tn = int(input())
	n = tn - 1
	A = []
	while n > 0:
		k = math.ceil(math.sqrt(n)) ** 2
		l = k - n
		A = [n - i for i in range(n - l + 1)] + A
		n = l - 1
	if len(A) < tn:
		A = [0] + A
	for i in A:
		print(i, end=' ')
	print()


t = int(input())
while t:
	t -= 1
	n = int(input())
	ans = [0] * n
	i = n - 1
	while i >= 0:
		for j in range(0, i + 1):
			val = (i + j) ** 0.5
			if int(val) == val:
				break
		for k in range(j, i + 1):
			ans[k] = i + j - k
		i = j - 1
	print(*ans)


import math
for _ in range(int(input())):
	n = int(input())
	p = [-1 for i in range(n)]
	while n > 0:
		a = int(math.sqrt(n - 1))
		if a * a == n - 1:
			for i in range(n):
				p[i] = n - i - 1
			break
		else:
			q = (a + 1) * (a + 1)
			for i in range(q - n + 1, n):
				p[i] = q - i
			n = q - n + 1
	print(*p)


import math
t = int(input())
for i in range(t):
	n = int(input())
	max_square = math.floor(math.sqrt(2 * n - 1))
	arr = [a for a in range(n)]
	j = n - 1
	solved = True
	while j > 0 and max_square >= 0:
		req_idx = max_square * max_square - arr[j]
		if req_idx > n:
			solved = False
			break
		elif req_idx < 0 or req_idx > j:
			max_square -= 1
		elif req_idx >= 0:
			dist = (j + 1 - req_idx) // 2
			for k in range(dist):
				temp = arr[req_idx + k]
				arr[req_idx + k] = arr[j - k]
				arr[j - k] = temp
			max_square = max_square - 1
			j = req_idx - 1
	if solved == False:
		print(-1)
	else:
		for num in arr:
			print(num, end=' ')
		print()


from math import sqrt, floor
t = int(input())
for _ in range(t):
	n = int(input())
	i = n - 1
	perm = []
	while i >= 0:
		nearst_square = floor(sqrt(2 * i)) ** 2
		if 2 * i == nearst_square:
			perm = [i] + perm
			i -= 1
			continue
		diff = nearst_square - i
		perm = [x for x in range(i, diff - 1, -1)] + perm
		i = diff - 1
	for el in perm:
		print(el, end=' ')
	print()


import math

def perfect(n):
	x = math.floor(math.sqrt(n - 1))
	l = [0] * n
	y = x ** 2
	if y == n - 1:
		x = x
	else:
		x = x + 1
		y = x ** 2
	for i in range(n - 1, -1, -1):
		f = 0
		while f == 0:
			if y - i <= n - 1 and l[y - i] == 0:
				l[y - i] = i
				f = 1
			else:
				y = (x - 1) ** 2
				x = x - 1
	return l
for i in range(int(input())):
	n = int(input())
	a = perfect(n)
	print(*a)


try:
	d = {}
	for i in range(1000):
		d[i * i] = 1
	for _ in range(int(input())):
		n = int(input())
		n = n - 1
		l = [0] * (n + 1)
		while n > -1:
			for i in d:
				if n <= i:
					l[n] = i - n
					l[i - n] = n
					n = i - n - 1
					break
		if l[0] == 0:
			k = 1
		else:
			k = 0
		for i in range(k, len(l)):
			if l[i] == 0:
				l[i] = l[i - 1] - 1
		for i in range(len(l)):
			print(l[i], end=' ')
		print()
except:
	pass


t = int(input())
for i in range(t):
	n = int(input())
	l = [0] * n
	v = int((n - 1) ** 0.5)
	if v * v == n - 1:
		p = v
	else:
		p = v + 1
	for j in range(n - 1, -1, -1):
		f = 0
		while f == 0:
			if p * p - j <= n - 1 and l[p * p - j] == 0:
				l[p * p - j] = j
				f = 1
			else:
				p -= 1
	print(*l)


def perfsqr(a):
	if int(a ** 0.5) == a ** 0.5:
		return True
	else:
		return False

def recur(n, l):
	if perfsqr(n) == True:
		for i in range(n + 1):
			l.append(i)
	else:
		t = int(n ** 0.5) + 1
		diff = t ** 2 - n
		for i in range(diff, n + 1):
			l.append(i)
		return recur(diff - 1, l)
	return l
for _ in range(int(input())):
	num = int(input())
	l = []
	recur(num - 1, l)
	for i in l[::-1]:
		print(i, end=' ')
	print()


t = int(input())
q = [i ** 2 for i in range(318)]
for _ in range(t):
	n = int(input())
	a = [0] * n
	flag = True
	while n > 0:
		qq = -1
		for i in range(318):
			if q[i] >= n - 1 and q[i] - n + 1 <= n - 1:
				qq = q[i]
				break
			elif q[i] - n + 1 > n - 1:
				flag = False
				break
		if not flag:
			break
		if qq > n - 1:
			for i in range(n - 1, qq - n, -1):
				a[i] = qq - i
		else:
			for i in range(n):
				a[i] = n - 1 - i
		n = qq - n + 1
	if not flag:
		print(-1)
	else:
		print(*a)


from math import sqrt
for t in range(int(input())):
	n = int(input())
	a = [*(x for x in range(n))]
	e = n - 1
	b = []
	while e > -1:
		r = e
		while True:
			if sqrt(r) != round(sqrt(r)):
				r += 1
			else:
				b.append((r - e, e))
				break
		e = r - e - 1
	for i in b:
		x = i[0]
		y = i[1]
		while x < y:
			tm = a[x]
			a[x] = a[y]
			a[y] = tm
			x += 1
			y -= 1
	print(*a)


import math

def sq(num):
	if math.sqrt(num).is_integer():
		return int(math.sqrt(num))
	else:
		x = int(math.sqrt(num))
		return x
for _ in range(int(input())):
	n = int(input())
	ans = [0] * n
	lst = list(range(n - 1, -1, -1))
	num = 2 * n - 2
	sqq = sq(num)
	d = dict()
	for i in range(n - 1, -1, -1):
		tnum = sqq ** 2 - i
		if tnum <= n - 1 and d.get(tnum, 'Nan') == 'Nan':
			ans[i] = tnum
			d[tnum] = 1
		else:
			f = True
			while f:
				sqq -= 1
				tnum = sqq ** 2 - i
				if tnum <= n - 1 and d.get(tnum, 'Nan') == 'Nan':
					d[tnum] = 1
					f = False
					ans[i] = tnum
	print(*ans)


from math import sqrt
for _ in range(int(input())):
	n = int(input())
	ans = int(sqrt((n - 1) * 2))
	s = set()
	l = [0] * n
	for i in range(n - 1, -1, -1):
		while ans * ans - i > n - 1 or ans * ans - i in s:
			ans -= 1
		x = ans * ans - i
		s.add(x)
		l[i] = x
	if len(l) == n:
		print(*l)
	else:
		print(-1)


T = int(input())
for _ in range(T):
	n = int(input())
	l = [i for i in range(n)]
	sq = [i * i for i in range(n)]
	j = [-1] * n
	m = n - 1
	s = set()
	pui = 0
	res = []
	for i in sq:
		if i >= m:
			break
		else:
			pui += 1
	res = sq[:pui + 2]
	res = res[::-1]
	l = l[::-1]
	q = 0
	v = n - 1
	i = 0
	while v >= 0:
		x = res[q] - v
		a = x
		if a > n - 1 or j[a] > -1:
			q += 1
			continue
		else:
			j[x] = v
		v -= 1
	print(*j)


import math

def solve(n):
	if n == 1:
		return [0]
	elif n == 2:
		return [1, 0]
	last = n - 1
	sqrt = math.sqrt(last)
	if sqrt == int(sqrt):
		return [x for x in range(last, -1, -1)]
	sqrt = int(sqrt) + 1
	nearest_psqr = sqrt * sqrt
	new_n = nearest_psqr - last
	res = solve(new_n)
	res.extend([x for x in range(last, new_n - 1, -1)])
	return res
t = int(input())
while t > 0:
	t -= 1
	n = int(input())
	res = solve(n)
	for val in res:
		print(val, end=' ')
	print()


import sys
import math
from collections import Counter

def gi():
	return list(map(int, sys.stdin.readline().strip().split()))

def gs():
	return sys.stdin.readline().strip()

def fun(a):
	ans = [-1] * a
	sq = []
	c = 0
	while c ** 2 <= 2 * a - 2:
		sq.append(c ** 2)
		c += 1
	l = len(sq)
	i = l - 1
	j = a - 1
	while j >= 0:
		if ans[j] != -1:
			j -= 1
		elif sq[i] - j < 0 or sq[i] - j > a - 1:
			i -= 1
		elif ans[sq[i] - j] != -1:
			i -= 1
		else:
			ans[sq[i] - j] = j
			ans[j] = sq[i] - j
			j -= 1
	return ans
for _ in range(int(input())):
	a = int(input())
	print(*fun(a))


testnum = int(input())
for testcount in range(testnum):
	n = int(input()) - 1
	l = []
	while n >= 0:
		l.append(n)
		nn = int(n ** 0.5)
		if nn ** 2 < n:
			nn += 1
		n = nn ** 2 - n - 1
	print(*range(l[-1], -1, -1), end='')
	for i in range(len(l) - 1, 0, -1):
		print('', *range(l[i - 1], l[i], -1), end='')
	print()


import math

def n_d(n):
	w = math.ceil(n ** 0.5) ** 2
	if n >= w // 2:
		return math.ceil(n ** 0.5) ** 2
	else:
		return -1
for _ in range(int(input())):
	n = int(input()) - 1
	a = []
	w0 = 100000000
	while n >= 0:
		w = n_d(n)
		if w == 1:
			a.append(0)
			a.append(1)
			n -= 2
		elif w == 0:
			a.append(0)
			n -= 1
		else:
			for i in range(w - n, n + 1):
				a.append(i)
			n = w - n - 1
	if 0 >= n:
		for i in range(len(a)):
			print(a[-1 - i], end=' ')
		print()
	else:
		print(-1)


c = int(input())
for i in range(c):
	n = int(input()) - 1
	arr = [0] * (n + 1)
	sq = (2 * n) ** (1 / 2) // 1
	j = n
	while j >= 0:
		if arr[j] == 0:
			x = int(sq ** 2 - j)
			if 0 <= x <= n and arr[x] == 0:
				arr[j] = x
				arr[x] = j
			else:
				sq = sq - 1
				j = j + 1
		j = j - 1
	for i in arr:
		print(i, end=' ')
	print()


def solve(n):
	if n < 2:
		L.append(n)
		return 1
	for i in range(n + 1):
		a = (n + i) ** 0.5
		if int(a) == a:
			if solve(i - 1):
				L.append(n)
				return 1
	else:
		return 0
for t in range(int(input())):
	n = int(input())
	L = []
	if solve(n - 1):
		cur = -1
		for i in L:
			for j in range(i, cur, -1):
				print(j, end=' ')
			cur = i
		print()
	else:
		print(-1)


import math

def swap(permutation: list, index_1, index_2):
	temp = permutation[index_1]
	permutation[index_1] = permutation[index_2]
	permutation[index_2] = temp

def good_checker(perm):
	for (i, value) in enumerate(perm):
		if math.sqrt(i + value) != math.ceil(math.sqrt(i + value)):
			return False
	return True

def build(n):
	if n == 0:
		return permutation
	next_perfect_square = math.ceil(math.sqrt(n - 1)) ** 2
	next_n = next_perfect_square - (n - 1)
	for i in range(n - 1, next_n, -1):
		solution = next_perfect_square - i
		permutation[solution] = i
		permutation[i] = solution
	return build(next_n)
test_cases = int(input())
ns = []
for test_case in range(test_cases):
	ns.append(int(input()))
for test_case in range(test_cases):
	n = ns[test_case]
	permutation = [x for x in range(n)]
	new_permutation = build(n)
	if good_checker(new_permutation):
		[print(x, end=' ') for x in new_permutation]
	else:
		print(-1)
	print()


from math import sqrt

class Sol:

	def __init__(self):
		self.d = {}

	def ans(self, n):
		if n in self.d:
			return self.d[n]
		else:
			x = sqrt(n - 1)
			if int(x) == x:
				self.d[n] = list(range(n - 1, -1, -1))
			else:
				y = (int(x) + 1) ** 2 - n + 1
				self.d[n] = self.ans(y) + list(range(n - 1, y - 1, -1))
			return self.d[n]
sol = Sol()
for _ in range(int(input())):
	n = int(input())
	print(*sol.ans(n))


from bisect import bisect_left as bl

def next_(num):
	return sq[bl(sq, num)]
sq = []
i = 0
while i * i <= 10 ** 6:
	sq.append(i * i)
	i += 1
for _ in range(int(input())):
	n = int(input())
	n -= 1
	ans = []
	while n >= 0:
		t = next_(n)
		diff = t - n
		for i in range(diff, n + 1):
			ans.append(i)
		n = diff - 1
	print(*ans[::-1])


def lb(x):
	l = -1
	r = len(sq)
	while r - l > 1:
		m = (l + r) // 2
		if sq[m] < x:
			l = m
		else:
			r = m
	return r
out = []
sq = []
i = 0
while i ** 2 <= 10 ** 5:
	sq.append(i ** 2)
	i += 1
sq.append(i ** 2)
for _ in range(int(input())):
	n = int(input())
	a = [0] * n
	m = n - 1
	while m > 0:
		s = sq[lb(m)]
		i = s - m
		while i < n and a[i] == 0:
			a[i] = m
			m -= 1
			i += 1
	out.append(a)
for i in out:
	print(*i)


import math
t = int(input())
for i in range(t):
	n = int(input())
	lst = [j for j in range(n)]
	ed = n - 1
	while ed >= 0:
		tmp = int(math.ceil(math.sqrt(ed)))
		st = tmp * tmp - ed
		i1 = st
		i2 = ed
		while i1 < i2:
			(lst[i1], lst[i2]) = (lst[i2], lst[i1])
			i1 += 1
			i2 += -1
		ed = st - 1
	for i in lst:
		print(i, end=' ')
	print('\n')


from math import sqrt, ceil

def checker(permutation):
	for (i, value) in enumerate(permutation):
		if sqrt(value + i) != ceil(sqrt(i + value)):
			return False
	return True

def build(num, permutation):
	if num == 0:
		return permutation
	square = ceil(sqrt(num - 1)) ** 2
	next_n = square - (num - 1)
	for i in range(num - 1, next_n, -1):
		solution = square - i
		permutation[solution] = i
		permutation[i] = solution
	return build(next_n, permutation)
for _ in range(int(input())):
	n = int(input())
	perm = list(range(n))
	perm = build(n, perm)
	if checker(perm):
		print(*perm)
	else:
		print(-1)