Given a positive integer N, find an array A = [A_{1}, A_{2}, \ldots, A_{N}] of length N consisting of distinct integers from 1 to 10^{9}, such that the following condition is satisfied for each subarray [A_{L}, A_{L+1}, \ldots, A_{r}] (1≤ L ≤ R≤ N):

The sum of elements in the subarray is divisible by its length i.e. A_{L} + A_{L+1} + \ldots + A_{R} is divisible by R - L + 1.

It can be proved that such an array always exists under given constraints.

If there are multiple possible arrays, you may print any of them.

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

- The first line of the input contains a single integer T, denoting the number of test cases. The description of T test cases follows.
- Each test case consists of a single line containing one positive integer N, the length of the array A.

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

For each test case, print one line containing N space-separated integers, the contents of the array A.

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

$1 ≤ T ≤ 100$
$1 ≤ N ≤ 1000$
- Sum of $N$ over all test cases doesn't exceed $5000$

----- Sample Input 1 ------ 
3
1
2
3

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

----- explanation 1 ------ 
Test case $1$:

For array $A = [1]$,
- The sum of elements of the subarray $[1]$ is equal to $1$ which is divisible by $1$, the length of this subarray.

Test case $2$:

For array $A = [1, 3]$,
- The sum of elements of the subarray $[1]$ is equal to $1$ which is divisible by $1$, the length of this subarray.
- The sum of elements of the subarray $[3]$ is equal to $3$ which is divisible by $1$, the length of this subarray.
- The sum of elements of the subarray $[1, 3]$ is equal to $4$ which is divisible by $2$, the length of this subarray.

Test case $3$:

For array $A = [4, 2, 6]$,
- The sum of elements of the subarray $[4]$ is equal to $4$ which is divisible by $1$, the length of this subarray.
- The sum of elements of the subarray $[2]$ is equal to $2$ which is divisible by $1$, the length of this subarray.
- The sum of elements of the subarray $[6]$ is equal to $6$ which is divisible by $1$, the length of this subarray.
- The sum of elements of the subarray $[4, 2]$ is equal to $6$ which is divisible by $2$, the length of this subarray.
- The sum of elements of the subarray $[2, 6]$ is equal to $8$ which is divisible by $2$, the length of this subarray.
- The sum of elements of the subarray $[4, 2, 6]$ is equal to $12$ which is divisible by $3$, the length of this subarray.

Difficulty: MEDIUM
Tags: Constructive algorithms

Data structures

Ad-hoc
Skill types: Data structures

Starter code:

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


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


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


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


for i in range(int(input())):
	n = int(input())
	if n == 1:
		print(1)
		continue
	arr = []
	if n & 1 == 0:
		c = 1
		while n > 0:
			print(c, end=' ')
			c += 2
			n -= 1
	else:
		c = 2
		while n > 0:
			print(c, end=' ')
			c += 2
			n -= 1
	print()


def subArrayProblem(n):
	arr = []
	rangeStep = 2
	rangeStart = 2
	rangeEnd = n + n + 1
	if n % 2 == 0:
		rangeStep = 2
		rangeStart = 1
		rangeEnd = n + n
	if n == 1:
		arr.append(1)
		return arr
	for i in range(rangeStart, rangeEnd, rangeStep):
		arr.append(i)
	return arr
t = int(input())
for i in range(t):
	n = int(input())
	for j in subArrayProblem(n):
		print(j, end=' ')
	print()