You are given an integer N. 

Construct a permutation P of length N such that 
For all i (1 ≤ i ≤ N-1), i divides abs(P_{i+1}-P_{i}).

Recall that a permutation of length N is an array where every integer from 1 to N occurs exactly once.

It can be proven that for the given constraints at least one such P always exists.

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

- The first line of input contains a single integer T, denoting the number of test cases. The description of T test cases follow.
- The only line of each test case contains an integer N - the length of the array to be constructed.

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

For each test case, output a single line containing N space-separated integers P_{1}, P_{2}, \dots, P_{N}, denoting the elements of the array P.

If there exist multiple such arrays, print any.

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

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

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

----- Sample Output 1 ------ 
1 2
2 1 3

----- explanation 1 ------ 
Test case 1: A possible array satisfying all the conditions is $[1, 2]$:
- For $i=1$: $abs(A_{2}-A_{1})=abs(2-1)=1$ is divisible by $1$.

Test case 2: A possible array satisfying all the conditions is $[2, 1, 3]$:
- For $i=1$: $abs(A_{2}-A_{1})=abs(1-2)=1$ is divisible by $1$.
- For $i=2$: $abs(A_{3}-A_{2})=abs(3-1)=2$ is divisible by $2$.

Difficulty: EASY
Tags: Implementation

Starter code:

Solutions:
for _ in range(int(input())):
	n = int(input())
	ans = []
	for (x, y) in zip(range(n, n // 2 - 1, -1), range(1, n // 2 + 1)):
		ans.append(x)
		ans.append(y)
	else:
		if n % 2:
			ans.append(n // 2 + 1)
	print(*reversed(ans))


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


T = int(input())
for i in range(T):
	n = int(input())
	li = [0] * n
	if n % 2 == 1:
		val1 = int((n + 1) / 2)
	else:
		val1 = int(n / 2)
	val2 = val1 + 1
	for j in range(1, n + 1):
		if j % 2 == 1:
			li[j - 1] = val1
			val1 = val1 - 1
		else:
			li[j - 1] = val2
			val2 = val2 + 1
	print(*li, sep=' ')


T = int(input())
for t in range(T):
	arr = []
	a = int(input())
	odd_check = a
	if a % 2 == 1:
		a = a + 1
	for i in range(1, a + 1):
		arr.append(i)
	val = a // 2
	val1 = val + 1
	for j in range(0, a, 2):
		arr[j] = val
		val = val - 1
		arr[j + 1] = val1
		val1 = val1 + 1
	if odd_check % 2 == 1:
		arr.remove(arr[odd_check])
	print(*arr)


T = int(input())
while T != 0:
	N = int(input())
	use = N
	string = '_' + str(N)
	for i in range(N - 1, 0, -1):
		if (N - i) % 2 != 0:
			string = string + '_' + str(use - i)
			use = use - i
		else:
			string = string + '_' + str(use + i)
			use = use + i
	k = ''
	for i in range(len(string) - 1, -1, -1):
		if string[i] != '_':
			k = k + string[i]
		else:
			if len(k) > 1:
				for j in range(len(k) - 1, -1, -1):
					print(k[j], end='')
				print(end=' ')
			else:
				print(k, end=' ')
			k = ''
	print()
	T -= 1


T = int(input())
for i in range(T):
	N = int(input())
	l = []
	s = 0
	for i in range(N):
		if i % 2:
			l.append(s)
		else:
			l.append(N - s)
			s += 1
	print(' '.join((str(a) for a in l[::-1])))


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


import math
T = int(input())
for i in range(T):
	N = int(input())
	parr = []
	odd = 1
	even = N
	for j in range(N):
		if j % 2 == 0:
			parr.insert(0, even)
			even -= 1
		else:
			parr.insert(0, odd)
			odd += 1
	print(*parr)


for _ in range(int(input())):
	n = int(input())
	if n < 4:
		if n == 3:
			l = [2, 1, 3]
		if n == 2:
			l = [1, 2]
		elif n == 1:
			l = [1]
	else:
		if n % 2 == 0:
			l = [n // 2, n // 2 + 1]
		else:
			l = [n // 2 + 1, n // 2 + 1 + 1]
		for i in range(2, n - 1):
			v2 = l[-1] + 1
			v1 = l[-2] - 1
			l.append(v1)
			l.append(v2)
		l = l[0:n]
	print(*l, sep=' ')


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


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


t = int(input())
for dummy in range(t):
	n = int(input())
	res = []
	for i in range(n // 2):
		res += [n - i, i + 1]
	if n % 2 == 1:
		res.append(i + 2)
	res.reverse()
	print(str(res).strip('[]').replace(',', ''))


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


import math
t = int(input())
for i in range(t):
	n = int(input())
	j = 1
	ans = 0
	li = []
	if n % 2 == 0:
		for i in range(n // 2 + 1, n + 1):
			li.append(0)
			li.append(i)
	else:
		for i in range(n // 2 + 1, n + 1):
			li.append(i)
			li.append(0)
		li.pop()
	temp = n // 2
	if n % 2 == 0:
		for i in range(len(li)):
			if li[i] == 0:
				li[i] = temp
				temp -= 1
	else:
		for i in range(len(li)):
			if li[i] == 0:
				li[i] = temp
				temp -= 1
	for i in li:
		print(i, end=' ')
	print()


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


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


T = int(input())
for _ in range(T):
	n = int(input())
	ans = []
	for i in range(n // 2):
		ans.append(n - i)
		ans.append(i + 1)
	if n % 2 == 1:
		ans.append(i + 2)
	ans.reverse()
	print(str(ans).strip('[]').replace(',', ' '))


for i in range(int(input())):
	n = int(input())
	l = []
	for j in range(1, n + 1):
		l.append(j)
	r = int(n / 2)
	l1 = l[:r]
	l2 = l[r:]
	l1.reverse()
	c = 1
	for j in range(int(n / 2)):
		l2.insert(c, l1[j])
		c = c + 2
	for x in l2:
		print(x, end=' ')
	print()


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


t = int(input())
while t:
	n = int(input())
	arr = [0] * n
	arr[n - 1] = n
	chng = True
	for i in range(n - 2, -1, -1):
		if chng:
			arr[i] = arr[i + 1] - (i + 1)
			chng = False
		else:
			arr[i] = arr[i + 1] + (i + 1)
			chng = True
	print(*arr)
	t -= 1


for _ in range(int(input())):
	n = int(input().strip())
	result = []
	for i in range(int(n / 2)):
		result.append(n - i)
		result.append(i + 1)
	if n % 2 == 1:
		result.append(i + 2)
	print(*reversed(result))


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


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


t = int(input())
while t != 0:
	n = int(input())
	(s, p) = (0, 0)
	if n % 2 == 0:
		s = n // 2
		p = s + 1
	else:
		print(n // 2 + 1, end=' ')
		s = n // 2
		p = s + 2
	while p <= n:
		print(s, p, end=' ')
		p += 1
		s -= 1
	print()
	t -= 1


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


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


for _ in range(int(input())):
	N = int(input())
	P = [N]
	for i in range(N - 1, 0, -1):
		c = P[-1] - i
		if c > 0 and c not in P:
			P.append(abs(P[-1] - i))
		else:
			P.append(abs(P[-1] + i))
	print(' '.join(list(map(str, P[::-1]))))


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


T = int(input())
for x in range(T):
	n = int(input())
	ans = []
	if n & 1:
		for i in range(n // 2):
			ans.append(n - i)
			ans.append(i + 1)
		ans.append(n // 2 + 1)
	else:
		for i in range(n // 2):
			ans.append(n - i)
			ans.append(i + 1)
	print(*ans[::-1])


for i in range(int(input())):
	n = int(input())
	l = [0] * n
	t = n
	for i in range(n - 1, -1, -2):
		l[i] = t
		t -= 1
	t = 1
	for i in range(n - 2, -1, -2):
		l[i] = t
		t += 1
	print(*l)


for i in range(int(input())):
	n = int(input())
	a = [0] * n
	if n % 2 == 1:
		n += 1
		p = n // 2
		q = p + 1
		j = 0
		k = 1
		while j < n:
			a[j] = p
			p -= 1
			j += 2
		while k < n - 1:
			a[k] = q
			k += 2
			q += 1
	else:
		p = n // 2
		q = p + 1
		j = 0
		k = 1
		while j < n:
			a[j] = p
			p -= 1
			j += 2
		while k < n:
			a[k] = q
			k += 2
			q += 1
	print(*a)


from math import ceil

def solve(n):
	(a, b) = (1, n)
	lst = []
	for i in range(n):
		if i % 2 == 0:
			lst.append(b)
			b -= 1
		else:
			lst.append(a)
			a += 1
	print(*reversed(lst), sep=' ')
for _ in range(int(input())):
	solve(int(input()))


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


T = int(input())
for i in range(T):
	d = int(input())
	p = 0
	s = []
	for j in range(d):
		if j % 2 == 0:
			s.append(d - p)
			p = p + 1
		else:
			s.append(p)
	s.reverse()
	print(*s, sep=' ')


for _ in range(int(input())):
	N = int(input())
	K = 0
	lis = []
	for i in range(N):
		if i % 2 == 0:
			lis.append(N - K)
			K = K + 1
		else:
			lis.append(K)
	lis.reverse()
	print(*lis, sep=' ')


t = int(input())
while t > 0:
	n = int(input())
	list1 = []
	val1 = n
	val2 = 1
	if n == 1:
		print(1)
	else:
		for i in range(1, n + 1, 1):
			if i % 2 == 1:
				list1.append(val1)
				val1 = val1 - 1
			else:
				list1.append(val2)
				val2 = val2 + 1
		else:
			list1.reverse()
			for i in list1:
				print(i, end=' ')
	print()
	t = t - 1


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


def cutinhalf(arr):
	n = len(arr)
	if n % 2 == 0:
		mid = n // 2
		(l1, l2) = (arr[:mid], arr[mid:])
		return (l1, l2)
	else:
		mid = n // 2 + 1
		(l1, l2) = (arr[:mid], arr[mid:])
		return (l1, l2)
for tc in range(int(input())):
	n = int(input())
	arr = []
	ans = []
	for i in range(1, n + 1):
		arr.append(i)
	(l1, l2) = cutinhalf(arr)
	if not l2:
		ans = l1
	for i in range(len(l2)):
		ans.append(l1.pop())
		ans.append(l2[i])
	if l1:
		ans.append(l1[-1])
	print(*ans)


import math
t = int(input())
for _ in range(t):
	n = int(input())
	x = math.ceil(n / 2)
	a = []
	for i in range(x):
		a.append(x - i)
		a.append(x + i + 1)
	if n % 2 == 1:
		a.pop()
	print(' '.join(map(str, a)))