You are given an integer $n$. Find a sequence of $n$ distinct integers $a_1, a_2, \dots, a_n$ such that $1 \leq a_i \leq 10^9$ for all $i$ and $$\max(a_1, a_2, \dots, a_n) - \min(a_1, a_2, \dots, a_n)= \sqrt{a_1 + a_2 + \dots + a_n}.$$

It can be proven that there exists a sequence of distinct integers that satisfies all the conditions above.


-----Input-----

The first line of input contains $t$ ($1 \leq t \leq 10^4$) — the number of test cases.

The first and only line of each test case contains one integer $n$ ($2 \leq n \leq 3 \cdot 10^5$) — the length of the sequence you have to find.

The sum of $n$ over all test cases does not exceed $3 \cdot 10^5$.


-----Output-----

For each test case, output $n$ space-separated distinct integers $a_1, a_2, \dots, a_n$ satisfying the conditions in the statement.

If there are several possible answers, you can output any of them. Please remember that your integers must be distinct!


-----Examples-----

Input
3
2
5
4
Output
3 1
20 29 18 26 28
25 21 23 31


-----Note-----

In the first test case, the maximum is $3$, the minimum is $1$, the sum is $4$, and $3 - 1 = \sqrt{4}$.

In the second test case, the maximum is $29$, the minimum is $18$, the sum is $121$, and $29-18 = \sqrt{121}$.

For each test case, the integers are all distinct.

Difficulty: MEDIUM_HARD
Tags: Constructive algorithms

Sorting

Amortized analysis

Complete search

Mathematics
Skill types: Sorting

Amortized analysis

Complete search

Starter code:

Solutions:
for _ in range(int(input())):
	n = int(input())
	if n % 2:
		ad = n - (n + 1) // 2
		v = [i + ad + 2 for i in range(1, n + 1)]
		v[0] -= 1
		v[-1] += 1
		v[-2] += 1
		print(' '.join(map(str, v)))
	else:
		ad = (2 * n - 1 - (n + 1)) // 2
		v = [i + ad for i in range(1, n + 1)]
		for i in range(len(v) - n // 2, len(v)):
			v[i] += 1
		print(' '.join(map(str, v)))


for t in range(int(input())):
	n = int(input())
	if n % 2 == 0:
		ans = list(range(int(n / 2), n)) + list(range(n + 1, int(3 * n / 2) + 1))
	else:
		ans = list(range(n - int(n / 2) + 2, n + int(n / 2) + 3))
		ans[0] -= 1
		ans[-1] += 1
		ans[-2] += 1
	print(' '.join([str(x) for x in ans]))


import math
for _ in range(int(input())):
	n = int(input())
	nums = []
	if n & 1:
		nums = [i + 2 for i in range(n - n // 2, n + math.ceil(n / 2), 1)]
		nums[-1] += 1
		nums[0] -= 1
		nums[-2] += 1
	else:
		nums = [i for i in range(n // 2, n + n // 2 + 1) if i != n]
	print(' '.join([str(i) for i in nums]))


t = int(input())
for it in range(t):
	n = int(input())
	if n % 2:
		a = [i for i in range(n - n // 2, n + n // 2 + 1)]
		a = [a[i] + 2 for i in range(n)]
		a[0] -= 1
		a[n - 1] += 1
		a[n - 2] += 1
		a = [str(a[i]) for i in range(n)]
		print(' '.join(a))
	else:
		a = [i for i in range(n // 2, n // 2 + n)]
		for i in range(n // 2, n):
			a[i] += 1
		a = [str(a[i]) for i in range(n)]
		print(' '.join(a))


import sys
input = sys.stdin.readline

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

def readInt():
	return int(input())

def readInts():
	return map(int, input().split())

def readStr():
	return input().strip()

def solve():
	n = readInt()
	if n % 2:
		ans = [i + 2 for i in range(n - n // 2, n + n // 2 + 1)]
		(ans[0], ans[-1]) = (ans[0] - 1, ans[-1] + 1)
		ans[-2] += 1
		return ans
	else:
		ans = [n // 2 + i for i in range(n // 2)] + [n + i for i in range(1, n // 2 + 1)]
		return ans
	return
for _ in range(int(input())):
	print(*solve())


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 passer in range(inp()):
	n = inp()
	if n % 2 == 0:
		lst = []
		for i in range(n // 2, n // 2 + n + 1):
			if i != n:
				lst.append(i)
		print(*lst)
	else:
		lst = list(range(n // 2 + 3, n // 2 + n + 3))
		lst[-1] += 1
		lst[-2] += 1
		lst[0] -= 1
		print(*lst)


t = int(input())
for i in range(t):
	n = int(input())
	if n % 2 == 0:
		print(*[k for k in range(n // 2, n // 2 + n + 1) if k != n])
	else:
		a = list(range(n // 2 + 3, n // 2 + 3 + n))
		a[0] -= 1
		a[-1] += 1
		a[-2] += 1
		print(*a)


import os, sys, io, math
from array import *
from math import *
from bisect import *
from heapq import *
from functools import *
from itertools import *
from collections import *
I = lambda : [*map(int, sys.stdin.readline().split())]
IS = lambda : input()
IN = lambda : int(input())
IF = lambda : float(input())
for _ in range(IN()):
	n = IN()
	if n & 1:
		a = list(range(n // 2 + 3, n // 2 + 3 + n))
		a[0] -= 1
		a[-1] += 1
		a[-2] += 1
		print(*a)
	else:
		print(*[i for i in range(n // 2, n // 2 + n + 1) if i != n])


import sys
from collections import *
sys.setrecursionlimit(10 ** 5)
itr = (line for line in sys.stdin.read().strip().split('\n'))
INP = lambda : next(itr)

def ni():
	return int(INP())

def nl():
	return [int(_) for _ in INP().split()]
t = ni()
for _ in range(t):
	n = ni()
	if n == 2:
		print('3 1')
	elif n % 2 == 0:
		arr = [i for i in range(n - n // 2, n)]
		arr += [i for i in range(n + 1, n + n // 2 + 1)]
		print(*arr)
	else:
		r = n - 1
		diff = r // 2
		arr = [i + 2 for i in range(n - diff, n + diff + 1)]
		arr[0] -= 1
		arr[-1] += 1
		arr[-2] += 1
		print(*arr)


for _ in range(int(input())):
	n = int(input())
	if n % 2 == 0:
		print(*[i for i in range(n // 2, n // 2 + n + 1) if i != n])
	else:
		a = list(range(n // 2 + 3, n // 2 + 3 + n))
		a[0] -= 1
		a[-1] += 1
		a[-2] += 1
		print(*a)


for _ in range(int(input())):
	n = int(input())
	if n % 2 == 1:
		num = [x + (n - 1) // 2 + 2 for x in range(1, n + 1)]
		num[-1] += 1
		num[0] -= 1
		num[-2] += 1
	else:
		num = []
		for i in range(n // 2, n // 2 + n):
			if i != n:
				num.append(i)
		num.append(n // 2 + n)
	print(*num)


for _ in range(int(input())):
	n = int(input())
	if n % 2 == 0:
		ans = []
		val = n // 2
		cnt = 0
		while cnt < n:
			if val != n:
				ans.append(val)
				cnt += 1
			val += 1
		print(*ans)
	else:
		ans = []
		cnt = 0
		val = n // 2 + 1
		while cnt < n:
			ans.append(val)
			val += 1
			cnt += 1
		for i in range(len(ans)):
			ans[i] += 2
		ans[0] -= 1
		ans[-1] += 1
		ans[-2] += 1
		print(*ans)


for i in range(int(input())):
	n = int(input())
	a = [0] * n
	if n % 2 == 0:
		for j in range(n):
			a[j] = j + n // 2
		for j in range((n + 1) // 2, n):
			a[j] += 1
	else:
		for j in range(n):
			a[j] = j + n // 2 + 3
		a[0] -= 1
		a[n - 1] += 1
		a[n - 2] += 1
	for x in a:
		print(x, end=' ')
	print()