You are given an integer $n$. Pair the integers $1$ to $2n$ (i.e. each integer should be in exactly one pair) so that each sum of matched pairs is consecutive and distinct.

Formally, let $(a_i, b_i)$ be the pairs that you matched. $\{a_1, b_1, a_2, b_2, \ldots, a_n, b_n\}$ should be a permutation of $\{1, 2, \ldots, 2n\}$. Let the sorted list of $\{a_1+b_1, a_2+b_2, \ldots, a_n+b_n\}$ be $s_1 < s_2 < \ldots < s_n$. We must have $s_{i+1}-s_i = 1$ for $1 \le i \le n - 1$.


-----Input-----

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 500$). The description of the test cases follows.

For each test case, a single integer $n$ ($1 \leq n \leq 10^5$) is given.

It is guaranteed that the sum of $n$ over all test cases doesn't exceed $10^5$.


-----Output-----

For each test case, if it is impossible to make such a pairing, print "No".

Otherwise, print "Yes" followed by $n$ lines.

At each line, print two integers that are paired.

You can output the answer in any case (upper or lower). For example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as positive responses.

If there are multiple solutions, print any.


-----Examples-----

Input
4
1
2
3
4
Output
Yes
1 2
No
Yes
1 6
3 5
4 2
No


-----Note-----

For the third test case, each integer from $1$ to $6$ appears once. The sums of matched pairs are $4+2=6$, $1+6=7$, and $3+5=8$, which are consecutive and distinct.

Source: codeforces | Difficulty: EASY
Tags: Greedy algorithms

Mathematics

Constructive algorithms


Solutions:
a = int(input())
for i in range(a):
	N = int(input())
	if N % 2 == 0:
		print('NO')
	else:
		print('YES')
		c = N // 2
		c += 1
		j = 0
		for i in range(c):
			print(str(2 * N - i) + ' ' + str(j + 1))
			j += 2
		d = 2
		f = 2 * N - i
		for k in range(N - c):
			print(str(d) + ' ' + str(f - 1))
			d += 2
			f -= 1


for _ in range(int(input())):
	n = int(input())
	if n % 2 == 0:
		print('NO')
	else:
		a = 2 * n
		print('YES')
		for i in range(1, n + 1, 2):
			print(i, a)
			a = a - 1
		for i in range(2, n + 1, 2):
			print(i, a)
			a = a - 1


t = int(input())
while t > 0:
	t -= 1
	n = int(input())
	if n % 2 == 0:
		print('NO')
	else:
		print('YES')
		a = []
		m = (n - 1) // 2
		for i in range(1, (n - 1) // 2 + 1):
			print(i, 3 * m + i + 2)
		for i in range(m + 1, 2 * m + 2):
			print(i, m + i + 1)


for _ in range(int(input())):
	n = int(input())
	if n % 2:
		print('YES')
		k = 2 * n
		for i in range(1, n + 1, 2):
			print(i, k)
			k -= 1
		for i in range(2, n + 1, 2):
			print(i, k)
			k -= 1
	else:
		print('NO')


import math
import sys
input = sys.stdin.readline
import heapq

def put(arr, data):
	for i in arr:
		data[i] = data.get(i, 0) + 1
	return data

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()
	if n % 2 == 0:
		print('NO')
	else:
		print('YES')
		now = 2 * n
		for i in range(1, n + 1, 2):
			print(i, now)
			now -= 1
		for i in range(2, n, 2):
			print(i, now)
			now -= 1


N = int(input())
for i in range(N):
	num = int(input())
	if num % 2 == 0:
		print('NO')
	else:
		print('YES')
		tmp = num * 2
		for k in range(1, (num + 1) // 2 + 1):
			print(k, tmp)
			tmp -= 2
		tmp = num * 2 - 1
		for k in range((num + 1) // 2 + 1, num + 1):
			print(k, tmp)
			tmp -= 2


import sys
input = sys.stdin.readline

def solve():
	n = int(input().strip())
	if n % 2:
		temp = n * 2
		print('YES')
		for i in range(1, n + 1):
			print(i, temp)
			temp -= 2
			if temp == n - 1:
				temp = 2 * n - 1
	else:
		print('NO')

def main():
	t = int(input().strip())
	for _ in range(t):
		solve()
main()


for _ in range(int(input())):
	n = int(input())
	if not n % 2:
		print('NO')
	else:
		print('YES')
		(a, b) = (1, 2 * n)
		for i in range(n // 2 + 1):
			print(a, b)
			a += 1
			b -= 2
		b = 2 * n - 1
		for i in range(n // 2):
			print(a, b)
			a += 1
			b -= 2


def pairs(n):
	if n % 2 == 0:
		print('NO')
	else:
		print('YES')
		ind = n // 2
		endd = 2 * n
		while ind > 0:
			print(ind, endd)
			ind -= 1
			endd -= 1
		ind2 = n // 2 + 1
		endd2 = n + 1
		while ind2 <= n:
			print(ind2, endd2)
			ind2 += 1
			endd2 += 1
t = int(input())
for i in range(t):
	n = int(input())
	pairs(n)


def solve(n):
	for i in range(n // 2 + 1):
		print(i + 1, 2 * n - 2 * i)
	for i in range(n // 2):
		print(i + 1 + n // 2 + 1, 2 * n - 2 * i - 1)
for i in range(int(input())):
	n = int(input())
	if n % 2 == 0:
		print('NO')
	else:
		print('YES')
		solve(n)


t = int(input())
for _ in range(t):
	n = int(input())
	if n % 2 == 0:
		print('NO')
	else:
		print('YES')
		print(1, 2 * n)
		mid = 1 + 2 * n
		step = (n - 1) // 2
		cnt = 0
		for i in range(1 + step + 1, n + 1):
			print(i, mid + step - i - cnt)
			cnt += 1
		cnt = 0
		for j in range(2, n - step + 1):
			print(j, mid - 1 - j - cnt)
			cnt += 1


for _ in range(int(input())):
	n = int(input())
	if n % 2 == 0:
		print('NO')
	else:
		print('YES')
		x = 2 * n + 1 - (n - 1) // 2
		(l, r) = (1, 2 * n)
		while l + r >= x:
			print(l, r)
			l += 1
			r -= 2
		r = 2 * n - 1
		while l <= r:
			print(l, r)
			l += 1
			r -= 2


t = int(input())
for i in range(t):
	n = int(input())
	if n % 2 == 0:
		print('NO')
	else:
		print('YES')
		i = 1
		j = 2 * n
		for k in range(n // 2 + 1):
			print(i, j)
			i += 1
			j -= 2
		j = 2 * n - 1
		for k in range(n // 2):
			print(i, j)
			i += 1
			j -= 2


import math
T = int(input())
for i in range(T):
	n = int(input())
	if n & 1:
		print('YES')
		for i in range(1, int(math.ceil(n / 2)) + 1):
			print(i * 2 - 1, n * 2 - i + 1)
		for i in range(1, int(math.ceil(n / 2))):
			print(i * 2, n * 2 - int(math.ceil(n / 2)) - i + 1)
	else:
		print('NO')


import math

def main():
	t = int(input().strip())
	while t > 0:
		t -= 1
		n = int(input().strip())
		if n % 2 == 1:
			print('YES')
			for i in range(1, math.ceil(n / 2) + 1):
				print(i + i - 1, n - i + 1 + n)
			for i in range(1, math.ceil(n / 2)):
				print(i + i, n - math.ceil(n / 2) - i + 1 + n)
		else:
			print('NO')
main()


t = int(input())
for i in range(t):
	n = int(input())
	if n % 2 == 0:
		print('NO')
	else:
		print('YES')
		if n == 1:
			print(1, 2)
		else:
			l1 = [i for i in range(2 * n, n, -1)]
			l2 = []
			l3 = []
			for i in range(1, n + 1):
				if i % 2 == 0:
					l3.append(i)
				else:
					l2.append(i)
			l2 += l3
			for i in range(n):
				print(l1[i], l2[i])


for _ in range(int(input())):
	n = int(input())
	if n % 2 == 0:
		print('NO')
		continue
	print('YES')
	for i in range(1, (n + 3) // 2):
		print(i, 2 * (n - i + 1))
	for i in range(n, (n + 1) // 2, -1):
		print(i, 2 * (n - i + 1) + n)


from collections import Counter
import math
for _ in range(int(input())):
	n = int(input())
	if n % 2 == 0:
		print('NO')
	else:
		print('YES')
		x = 2 * n + 1
		y = x - n // 2
		for i in range(1, n + 1):
			if i % 2 == 0:
				l = [i, y - i]
				print(*l)
				y = y + 1
		for i in range(1, n + 1):
			if i % 2 != 0:
				l = [i, y - i]
				print(*l)
				y = y + 1


def intRd():
	return int(input())

def lstRd():
	return list(map(int, input().split()))
for _ in range(intRd()):
	n = intRd()
	if n & 1:
		print('YES')
		mid = 1 + 2 * n
		print(1, 2 * n)
		sm = True
		sml = 0
		lml = 0
		for i in range(2, n + 1):
			if sm:
				j = mid - n // 2 + sml - i
				print(i, j)
				sml += 1
				sm = False
			else:
				j = mid + lml + 1 - i
				print(i, j)
				lml += 1
				sm = True
	else:
		print('NO')


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