You are given an integer N. Your task is to generate a permutation P of size N, such that:

For all (1< i≤ N), \sum_{j = 1}^{i} P_{j} is not divisible by i.  
In other words, the sum of prefix of length i (i> 1) should not be divisible by i.

In case multiple such permutations exist, print any. If no such permutation exists, print -1 instead.

Note that a permutation of size N contains all integers from 1 to N exactly once.

------ Input Format ------ 

- The first line of input will contain a single integer T, denoting the number of test cases.
- Each test case consists a single integer N — the size of the permutation.

------ Output Format ------ 

For each test case, output on a new line, N space separated integers, denoting the required permutation. 

In case multiple such permutations exist, print any. If no such permutation exists, print -1 instead.

------ Constraints ------ 

$1 ≤ T ≤ 1000$
$2 ≤ N ≤ 10^{4}$
- The sum of $N$ over all test cases won't exceed $2\cdot 10^{5}$.

----- Sample Input 1 ------ 
3
4
6
7

----- Sample Output 1 ------ 
3 4 1 2
1 2 4 6 3 5
-1

----- explanation 1 ------ 
Test case $1$: A possible permutation satisfying the given conditions is $P = [3, 4, 1, 2]$.
- For $i = 2$: The prefix sum is $3+4=7$, which is not divisible by $2$.
- For $i = 3$: The prefix sum is $3+4+1=8$, which is not divisible by $3$.
- For $i = 4$: The prefix sum is $3+4+1+2=10$, which is not divisible by $4$.

Test case $2$: A possible permutation satisfying the given conditions is $P = [1, 2, 4, 6, 3, 5]$.
- For $i = 2$: The prefix sum is $1+2=3$, which is not divisible by $2$.
- For $i = 3$: The prefix sum is $1+2+4=7$, which is not divisible by $3$.
- For $i = 4$: The prefix sum is $1+2+4+6=13$, which is not divisible by $4$.
- For $i = 5$: The prefix sum is $1+2+4+6+3=16$, which is not divisible by $5$.
- For $i = 6$: The prefix sum is $1+2+4+6+3+5=21$, which is not divisible by $6$.

Test case $3$: It can be proven that no permutation of length $7$ satisfies the given conditions.

Difficulty: EASY
Tags: Constructive algorithms

Starter code:

Solutions:
for kjds in range(int(input())):
	n = int(input())
	l = []
	if n % 2 == 1:
		print(-1)
		continue
	for g in range(1, n + 1):
		l.append(g)
	a = 0
	for f in range(n // 2):
		temp = l[a]
		l[a] = l[a + 1]
		l[a + 1] = temp
		a += 2
	print(*l)


for _ in range(int(input())):
	n = int(input())
	odd = 1
	even = 2
	if n % 2 == 0:
		pass
	else:
		print(-1)
		continue
	for i in range(n):
		if i % 2 == 0:
			print(even, end=' ')
			even += 2
		else:
			print(odd, end=' ')
			odd += 2
	print()


for _ in range(int(input())):
	n = int(input())
	if n % 2 == 1:
		print(-1)
		continue
	arr = [i for i in range(1, n + 1)]
	for i in range(0, n, 2):
		(arr[i + 1], arr[i]) = (arr[i], arr[i + 1])
	print(*arr)


for _ in range(int(input())):
	n = int(input())
	l = list(range(3, n + 1))
	p = 0
	temp = [1, 2]
	k = 3
	if (sum(temp) + sum(l)) % n == 0:
		print(-1)
	else:
		while len(temp) < n:
			if (sum(temp) + l[p]) % k != 0 and l[p] not in temp:
				temp.append(l[p])
				k += 1
			elif p == len(l) - 1:
				p = 0
			else:
				p += 1
		else:
			print(' '.join(map(str, temp)))


t = int(input())
for _ in range(t):
	n = int(input())
	if n % 2:
		print(-1)
	else:
		ans = []
		for i in range(1, n + 1, 2):
			ans.append(i + 1)
			ans.append(i)
		print(*ans)


def generate_permutation(n):
	permutation = list(range(1, n + 1))
	for i in range(1, n):
		prefix_sum = sum(permutation[:i])
		if prefix_sum % (i + 1) == 0:
			if i == n - 1:
				return [-1]
			(permutation[i], permutation[i + 1]) = (permutation[i + 1], permutation[i])
	return permutation
t = int(input())
for _ in range(t):
	n = int(input())
	permutation = generate_permutation(n)
	print(*permutation)


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


for i in range(int(input())):
	n = int(input())
	if n & 1:
		print(-1)
	else:
		for i in range(1, n + 1):
			if i & 1:
				print(i + 1, end=' ')
			else:
				print(i - 1, end=' ')
		print()


t = int(input())
for _ in range(t):
	N = int(input())
	if N & 1 == 1:
		print(-1)
	else:
		ls = [i for i in range(1, N + 1)]
		i = 2
		while i + 1 < len(ls):
			(ls[i], ls[i + 1]) = (ls[i + 1], ls[i])
			i += 2
		print(' '.join((str(item) for item in ls)))


for _ in range(int(input())):
	n = int(input())
	if n % 2 != 0:
		print(-1)
	else:
		print('1 2', end=' ')
		for i in range(4, n + 1, 2):
			print(i, i - 1, end=' ')
		print()


t = int(input())
for _ in range(t):
	n = int(input())
	al = [int(x) for x in range(1, n)]
	res = [n]
	(prefix, flag) = (n, 0)
	for i in range(2, n + 1):
		for x in al:
			val = prefix + x
			if val % i != 0:
				prefix = val
				res.append(x)
				al.remove(x)
				break
			if len(al) == 1:
				flag = 1
				print('-1')
	if flag == 0:
		print(' '.join(map(str, res)))


testcases = int(input())
for eachcase in range(testcases):
	length = int(input())
	if length & 1:
		print(-1)
	else:
		nums = []
		for index in range(1, length + 1, 2):
			nums.append(index + 1)
			nums.append(index)
		print(*nums)


testcases = int(input())
for eachcase in range(testcases):
	length = int(input())
	if length & 1:
		print(-1)
	else:
		nums = [i for i in range(1, length + 1)]
		total = sum(nums)
		index = length - 1
		pause = length - 1
		while index >= 0 and pause >= 2:
			if (total - nums[index]) % pause != 0:
				(nums[index], nums[pause]) = (nums[pause], nums[index])
				total -= nums[pause]
				index = pause
				pause -= 1
			index -= 1
		print(*nums)


test = int(input())
for i in range(test):
	x = int(input())
	if x & 1 == 1:
		print(-1)
	else:
		ar = [0] * x
		y = 2
		xz = 1
		for i in range(x):
			if i % 2 == 0:
				ar[i] = y
				y += 2
			else:
				ar[i] = xz
				xz += 2
		print(*ar)


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


for tc in range(int(input())):
	n = int(input())
	if n % 2 != 0:
		print(-1)
		continue
	else:
		for i in range(1, n // 2 + 1):
			print(2 * i, end=' ')
			print(2 * i - 1, end=' ')
	print('\n')


t = int(input())
for _ in range(t):
	n = int(input())
	temp = []
	l = []
	l.append(n)
	for i in range(1, n):
		temp.append(i)
	(prefix, flag) = (n, 0)
	for i in range(2, n + 1):
		for x in temp:
			val = prefix + x
			if val % i != 0:
				prefix = val
				l.append(x)
				temp.remove(x)
				break
			if len(temp) == 1:
				flag = 1
				print(-1)
	if flag == 0:
		for x in l:
			print(x, end=' ')
		print()


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


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


import sys
sys.setrecursionlimit(10 ** 7)
mod = 10 ** 9 + 7

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

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

def readStringList():
	return list(input())

def readStringListWithSpace():
	return list(input().split())

def readString():
	return input()
import math

def execute():
	for _ in range(readInt()):
		n = readInt()
		res = []
		if n % 2 == 0:
			for i in range(2, n + 1, 2):
				res.append(i)
				res.append(i - 1)
		else:
			res.append(-1)
		print(*res)
execute()


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


for i in range(int(input())):
	n = int(input())
	if n % 2 == 1:
		print(-1)
	elif n <= 0:
		print(-1)
	elif n == 2:
		a = [2, 1]
		i = 0
		while i < 2:
			if i == 0:
				print(a[i], end=' ')
			else:
				print(a[i])
			i += 1
	else:
		a = [1, 2]
		i = 2
		while i < n:
			a.append(i + 2)
			a.append(i + 1)
			i += 2
		i = 0
		while i < len(a):
			if i + 1 != len(a):
				print(a[i], end=' ')
			else:
				print(a[i])
			i += 1


A = []
for x in range(1, 10001, 2):
	A.extend([x + 1, x])
for _ in range(int(input())):
	N = int(input())
	print(*([-1] if N % 2 else A[:N]))


import sys
input = sys.stdin.readline

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

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

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

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

def outp(n):
	sys.stdout.write(str(n) + '\n')

def outlt(lst):
	sys.stdout.write(' '.join(map(str, lst)) + '\n')

def outplt(lst):
	sys.stdout.write('\n'.join(map(str, lst)))

def outpltlt(lst):
	sys.stdout.write('\n'.join(map(str, (' '.join(map(str, a)) for a in lst))))
A = []
for x in range(1, 10001, 2):
	A.append(x + 1)
	A.append(x)
for _ in range(inp()):
	N = inp()
	outlt([-1] if N % 2 else A[:N])


case = int(input())
for _ in range(case):
	n = int(input())
	if n & 1 == 1:
		print(-1)
		continue
	print(1, 2, end=' ')
	i = 3
	while i < n:
		print(i + 1, i, end=' ')
		i += 2
	print()


for _ in range(int(input())):
	n = int(input())
	if n == 2:
		print('1 2')
	elif n % 2 == 1:
		print(-1)
	else:
		print(1, end=' ')
		print(2, end=' ')
		for i in range(3, n, 2):
			print(i + 1, end=' ')
			print(i, end=' ')
	print()


for _ in range(int(input())):
	a = int(input())
	if a % 2 == 0:
		l = [str(i) for i in range(a, 0, -1)]
		for i in range(1, a, 2):
			(l[i], l[i - 1]) = (l[i - 1], l[i])
		print(' '.join(l))
	else:
		print(-1)


for _ in range(int(input())):
	n = int(input())
	t1 = ''
	if n % 2 == 1:
		print('-1')
	else:
		for i in range(1, n, 2):
			print(i + 1, i, end=' ')
		print()


t = int(input())
while t > 0:
	n = int(input())
	if n % 2 == 1:
		print(-1)
	else:
		for i in range(1, n, 2):
			print(i + 1, end=' ')
			print(i, end=' ')
		print()
	t = t - 1


t = int(input())
ans = []
for i in range(t):
	n = int(input())
	if n % 2:
		print(-1)
	else:
		for i in range(1, n + 1, 2):
			print(i + 1, i, end=' ')
		print()


for i in range(int(input())):
	n = int(input())
	arr = [i for i in range(1, n + 1)]
	if n % 2 != 0:
		print(-1)
	else:
		for i in range(1, n):
			if i % 2 != 0:
				print(arr[i], end=' ')
			else:
				print(arr[i - 2], end=' ')
		print(arr[i - 1])


def solve():
	n = int(input())
	if n % 2:
		print(-1)
		return
	a = list(range(n, 0, -1))
	for i in range(2, n, 2):
		(a[i], a[i + 1]) = (a[i + 1], a[i])
	print(' '.join(map(str, a)))
for _ in range(int(input())):
	solve()


t = int(input())
for _ in range(t):
	n = int(input())
	if n % 2 == 1:
		print(-1)
	else:
		l = [i for i in range(1, n + 1)]
		for i in range(2, len(l) - 1, 2):
			(l[i], l[i + 1]) = (l[i + 1], l[i])
		print(*l)


def rec(n):
	res = ''
	for i in range(1, n + 1):
		if i % 2 == 0:
			res += str(i - 1) + ' '
		else:
			res += str(i + 1) + ' '
	return res
for _ in range(int(input())):
	n = int(input())
	if n % 2 == 1:
		print(-1)
	else:
		print(rec(n))


def generate_permutation(N):
	odd_nums = [num for num in range(1, n + 1) if num % 2 != 0]
	even_numbers = [num for num in range(2, n + 1) if num % 2 == 0]
	p = []
	for i in range(int(N / 2)):
		p.append(even_numbers[i])
		p.append(odd_nums[i])
	return p
for i in range(int(input())):
	n = int(input())
	if n % 2 == 1:
		print('-1')
	else:
		print(*generate_permutation(n))


t = int(input())
for i in range(t):
	n = int(input())
	l = [x for x in range(1, n + 1)]
	if sum(l) % n == 0:
		print(-1)
	else:
		s = l[0]
		j = 1
		while j < n:
			if (s + l[j]) % (j + 1) != 0:
				s = s + l[j]
				j = j + 1
			else:
				l.append(l.pop(j))
		for k in l:
			print(k, end=' ')
		print()


import math
for t in range(int(input())):
	n = int(input())
	res = []
	if n % 2 == 0:
		for x in range(1, n + 1):
			if x % 2 == 0:
				res.append(str(x - 1))
			else:
				res.append(str(x + 1))
		print(' '.join(res))
	else:
		print(-1)


for _ in range(int(input())):
	a = int(input())
	if a % 2 != 0:
		print(-1)
	else:
		l = []
		for i in range(1, a + 1):
			l.append(i)
		for i in range(len(l) - 1):
			if i % 2 == 0:
				(l[i], l[i + 1]) = (l[i + 1], l[i])
		for i in l:
			print(i, end=' ')
		print()


for i in range(int(input())):
	n = int(input())
	a = []
	if n % 2:
		print('-1')
	else:
		for j in range(1, n + 1, 2):
			a.append(j + 1)
			a.append(j)
	print(*a)


from statistics import mode
for _ in range(int(input())):
	n = int(input())
	if n % 2 != 0:
		print(-1)
	else:
		even = []
		odd = []
		for i in range(1, n + 1):
			if i % 2 == 0:
				even.append(i)
			else:
				odd.append(i)
		ev = sorted(even, reverse=True)
		od = sorted(odd, reverse=True)
		ans = []
		for (x, y) in zip(od, ev):
			ans.append(x)
			ans.append(y)
		print(*ans)


s = int(input())
for i in range(s):
	a = int(input())
	if a % 2 != 0:
		print(-1)
	else:
		for j in range(1, a + 1, 2):
			n = j + 1
			print(n, end=' ')
			print(j, end=' ')
	print()


def soln(n: int) -> int:
	if n & 1:
		return [-1]
	arr = [i + 1 for i in range(n)]
	for i in range(0, n, 2):
		(arr[i], arr[i + 1]) = (arr[i + 1], arr[i])
	return arr
for _ in range(int(input())):
	n = int(input())
	print(*soln(n))


for i in range(int(input())):
	n = int(input())
	if n % 2 == 1:
		print(-1)
	else:
		print(1, 2, end=' ')
		for j in range(3, n + 1, 2):
			print(j + 1, j, end=' ')
	print()


for _ in range(int(input())):
	numberOfElements = int(input())
	if numberOfElements % 2:
		print(-1)
	else:
		numberList = []
		for i in range(1, numberOfElements + 1, 2):
			numberList.append(i + 1)
			numberList.append(i)
		print(*numberList)


t = int(input())
for i in range(t):
	z = int(input())
	p = []
	if z % 2 == 1:
		p.append(-1)
	else:
		for b in range(1, z + 1, 2):
			p.append(b + 1)
			p.append(b)
	for x in range(len(p)):
		if x == len(p) - 1:
			print(p[x])
		else:
			print(p[x], end=' ')


t = int(input())
for i in range(t):
	n = int(input())
	if n % 2 == 0:
		ans = []
		for j in range(1, n + 1, 2):
			ans.append(j + 1)
			ans.append(j)
		print(*ans)
	else:
		print(-1)


n = int(input())
for i in range(n):
	z = int(input())
	p = []
	if z % 2 == 1:
		print(-1)
	else:
		for b in range(1, z + 1, 2):
			p.append(b + 1)
			p.append(b)
		print(*p)


T = int(input())
for i in range(T):
	N = int(input())
	if N % 2:
		print(-1)
	else:
		for i in range(1, N + 1, 2):
			pass
			print(i + 1, i, end=' ')
		print()


for _ in range(int(input())):
	n = int(input())
	if n % 2 == 1:
		print(-1)
	else:
		l1 = list(range(1, n + 1, 2))
		l2 = list(range(2, n + 1, 2))
		for i in range(len(l1)):
			print(l2[i], l1[i], end=' ')
		print()


ans = []
nq = int(input())
for _ in range(nq):
	n = int(input())
	if n & 1:
		val = '-1'
	else:
		a = []
		i = n
		while i > 0:
			a.append(str(i - 1))
			a.append(str(i))
			i += -2
		val = ' '.join(a)
	ans.append(val)
print(*ans, sep='\n')


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


for _ in range(int(input())):
	val = int(input())
	if val % 2:
		print('-1')
	else:
		a = []
		for i in range(1, val + 1, 2):
			a.append(i + 1)
			a.append(i)
		print(*a)


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


t = int(input())
for i in range(t):
	n = int(input())
	if n % 2 == 0:
		p = [1]
		element = list(range(2, n + 1))
		while len(element) != 0:
			ele2 = element[0]
			p.append(ele2)
			ele = element.pop(0)
			if sum(p) % len(p) == 0:
				p.remove(ele2)
				element.append(ele)
		string = ''
		for ele in p:
			string += f'{ele} '
		print(string)
	else:
		print('-1')


for _ in range(int(input())):
	n = int(input())
	l = []
	if n % 2 != 0:
		print(-1)
		continue
	for i in range(1, n + 1, 2):
		l.append(i + 1)
		l.append(i)
	for i in range(len(l)):
		print(l[i], end=' ')
	print()


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


for t in range(int(input())):
	n = int(input())
	summ = n * (n + 1) // 2
	if summ % n == 0:
		print(-1)
		continue
	i = 2
	ans = [1, 2]
	summ = 3
	while i < n:
		if summ % (i + 1) == 0:
			ans.append(i + 2)
			ans.append(i + 1)
			summ += i + i + 3
			i += 2
		else:
			ans.append(i + 1)
			summ += i + 1
			i += 1
	print(*ans)


t = int(input())
for i in range(t):
	N = int(input())
	if N % 2 == 1:
		print(-1)
	else:
		A = []
		e = 2
		o = 1
		for j in range(N):
			if j % 2 == 0:
				A.append(e)
				e += 2
			else:
				A.append(o)
				o += 2
		print(*A)


for _ in range(int(input())):
	N = int(input())
	if N % 2 == 1:
		print(-1)
	else:
		ans = []
		for i in range(1, N + 1, 2):
			ans.append(i + 1)
			ans.append(i)
		print(*ans)