You are given an integer $n$.

Let's define $s(n)$ as the string "BAN" concatenated $n$ times. For example, $s(1)$ = "BAN", $s(3)$ = "BANBANBAN". Note that the length of the string $s(n)$ is equal to $3n$.

Consider $s(n)$. You can perform the following operation on $s(n)$ any number of times (possibly zero):

Select any two distinct indices $i$ and $j$ $(1 \leq i, j \leq 3n, i \ne j)$.

Then, swap $s(n)_i$ and $s(n)_j$.

You want the string "BAN" to not appear in $s(n)$ as a subsequence. What's the smallest number of operations you have to do to achieve this? Also, find one such shortest sequence of operations.

A string $a$ is a subsequence of a string $b$ if $a$ can be obtained from $b$ by deletion of several (possibly, zero or all) characters.


-----Input-----

The input consists of multiple test cases. The first line contains a single integer $t$ $(1 \leq t \leq 100)$  — the number of test cases. The description of the test cases follows.

The only line of each test case contains a single integer $n$ $(1 \leq n \leq 100)$.


-----Output-----

For each test case, in the first line output $m$ ($0 \le m \le 10^5$) — the minimum number of operations required. It's guaranteed that the objective is always achievable in at most $10^5$ operations under the constraints of the problem.

Then, output $m$ lines. The $k$-th of these lines should contain two integers $i_k$, $j_k$ $(1\leq i_k, j_k \leq 3n, i_k \ne j_k)$ denoting that you want to swap characters at indices $i_k$ and $j_k$ at the $k$-th operation.

After all $m$ operations, "BAN" must not appear in $s(n)$ as a subsequence.

If there are multiple possible answers, output any.


-----Examples-----

Input
2
1
2
Output
1
1 2
1
2 6


-----Note-----

In the first testcase, $s(1) = $ "BAN", we can swap $s(1)_1$ and $s(1)_2$, converting $s(1)$ to "ABN", which does not contain "BAN" as a subsequence.

In the second testcase, $s(2) = $ "BANBAN", we can swap $s(2)_2$ and $s(2)_6$, converting $s(2)$ to "BNNBAA", which does not contain "BAN" as a subsequence.

Difficulty: EASY
Tags: Constructive algorithms

Starter code:

Solutions:
t = int(input())
while t > 0:
	n = int(input())
	l = 1
	r = 3 * n
	print(n // 2 + n % 2)
	while r > l:
		print(l, r)
		l += 3
		r -= 3
	t -= 1


def main():
	tc = int(input())
	while tc > 0:
		a = int(input())
		print((a + 1) // 2)
		for i in range((a + 1) // 2):
			print(i * 3 + 1, a * 3 - (i * 3 + 1) + 1)
		tc -= 1
main()


import math
for _ in range(int(input())):
	n = int(input())
	print(math.ceil(n / 2))
	(l, r) = (1, n * 3)
	while l < r:
		print(l, r)
		l += 3
		r -= 3


for _ in range(int(input())):
	N = int(input())
	(st, en) = (1, 3 * N)
	op = (N + 1) // 2
	print(op)
	for i in range(op):
		print(st, en)
		st += 3
		en -= 3


for n in [*map(int, open(0))][1:]:
	print(n + 1 >> 1)
	i = 1
	j = n * 3
	while i < j:
		print(i, j)
		i += 3
		j -= 3


t = int(input())
for _ in range(t):
	n = int(input())
	l = 1
	r = 3 * n
	ans = []
	while l < r:
		ans.append('{} {}\n'.format(l, r))
		l += 3
		r -= 3
	print(len(ans))
	print(''.join(ans), end='')


test = int(input())
for i in range(test):
	n = int(input())
	ii = 0
	cnt = 0
	sst = 'BAN' * n
	j = len(sst) - 1
	ans = []
	while ii < j:
		if sst[ii] == 'B' and sst[j] == 'N':
			cnt += 1
			ans.append([ii + 1, j + 1])
			ii += 1
			j -= 1
		else:
			ii += 1
			j -= 1
	print(cnt)
	for i in ans:
		print(i[0], i[1])


for _ in range(int(input())):
	n = int(input())
	ans = []
	a = 1
	b = 3 * n
	cnt = 0
	while a < b:
		ans.append((a, b))
		n = n - 1
		b = 3 * n
		a += 3
	print(len(ans))
	for (i, j) in ans:
		print(i, j)


t = int(input())
for _ in range(t):
	n = int(input())
	M = 3 * n
	i = 0
	j = M - 1
	steps = []
	s = list('BAN' * n)
	while i < j:
		steps.append((i + 1, j + 1))
		(s[i], s[j]) = (s[j], s[i])
		i += 3
		j -= 3
	print(len(steps))
	for (i, j) in steps:
		print(i, j)


import sys
import math
num_test = int(input())
while num_test > 0:
	n = int(input())
	if n == 0:
		print(0)
	else:
		m = math.ceil(n / 2)
		print(m)
		(left, right) = (1, 3 * n)
		while m > 0:
			print(left, right)
			m -= 1
			left += 3
			right -= 3
	num_test -= 1


import math

def ban_ban(n):
	k = 0
	arr = []
	while len(arr) < math.ceil(n / 2):
		arr.append(str(k + 1) + ' ' + str(3 * n - k))
		k += 3
	print(len(arr))
	print(' '.join(arr))
num_cases = int(input())
for _ in range(num_cases):
	n = int(input())
	ban_ban(n)


t = int(input())
for _ in range(t):
	n = int(input())
	ans = (n + 1) // 2
	lst = [(3 * i + 1, 3 * (n - i)) for i in range(n // 2)]
	if n % 2 == 1:
		mid = 3 * (n // 2) + 1
		lst.append((mid, mid + 2))
	print(ans)
	for (x, y) in lst:
		print(x, y)


from math import ceil

def solve():
	n = int(input())
	print(ceil(n / 2))
	(s, e) = (1, 3 * n)
	while s < e:
		print(s, e)
		s += 3
		e -= 3
t = int(input())
for i in range(t):
	solve()


for j in range(int(input())):
	n = int(input())
	print(int((n + 1) / 2))
	for i in range(int((n + 1) / 2)):
		print(i * 3 + 1, n * 3 - i * 3)


for _ in range(int(input())):
	n = int(input())
	count = n // 2 + n % 2
	start = 1
	end = 3 * n
	print(count)
	for i in range(count):
		print(start, end)
		start += 3
		end -= 3


for _ in range(int(input())):
	n = int(input())
	x = -(-n // 2)
	print(x)
	for i in range(1, x + 1):
		print(i * 3 - 2, (n - i + 1) * 3)


for _ in range(int(input())):
	s = int(input())
	(l, r) = (0, s * 3 - 1)
	count = 0
	res = []
	while l < r:
		count += 1
		res.append(l + 1)
		res.append(r + 1)
		l += 3
		r -= 3
	print(count)
	print(*res)


import math
for _ in range(int(input())):
	n = int(input())
	q = math.ceil(n / 2)
	print(q)
	for i in range(q):
		print(3 * i + 1, 3 * n - 3 * i)


def main():
	n = int(input())
	for i in range(n):
		nums = int(input())
		if nums % 2 == 0:
			print(nums // 2)
		else:
			print(nums // 2 + 1)
			print(nums // 2 * 3 + 1, nums // 2 * 3 + 3)
		temp = nums // 2
		for j in range(temp):
			print(j * 3 + 1, (nums - j) * 3)
main()


testCase = int(input())
for i in range(testCase):
	n = int(input())
	m = max(n // 2, (n + 1) // 2)
	print(m)
	first = 1 - 3
	second = n * 3 + 3
	for it in range(m):
		first += 3
		second -= 3
		print(first, second)


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


for i in range(int(input())):
	a = int(input())
	print(int(a / 2 + a % 2))
	tem = 3 * (a % 2)
	for j in range(int(a / 2)):
		print((j + 1) * 3 - 2, (a - j) * 3)
	if tem == 3:
		print(3 * int(a / 2) + 1, 3 * int(a / 2) + 3)


test_cases = int(input())
for x in range(test_cases):
	a = int(input())
	b = a // 2 + a % 2
	print(b)
	last = 3 * a
	for i in range(b):
		print(str(3 * i + 1) + ' ' + str(last - 3 * i))


t = int(input())
for _ in range(t):
	n = int(input())
	print(n % 2 + n // 2)
	first = 1
	second = 3 * n
	for i in range(n % 2 + n // 2):
		print(first, second)
		first += 3
		second -= 3


for t in range(int(input())):
	n = int(input())
	str = 'BAN' * n
	print(int((n + 1) / 2))
	for i in range(int((n + 1) / 2)):
		print('{} {}'.format(3 * i + 1, 3 * n - 3 * i))


for jj in range(int(input())):
	n = int(input())
	if n % 2 == 0:
		s = n // 2
	else:
		s = n // 2 + 1
	print(s)
	for i in range(s):
		print(3 * i + 1, 3 * n - 3 * i)


for i in range(int(input())):
	n = int(input())
	if n == 1:
		print(1)
		print(1, 3)
	else:
		print(n // 2 + n % 2)
		k1 = 1
		k2 = n * 3
		while k1 < k2:
			print(k1, k2)
			k1 += 3
			k2 -= 3


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()
	ans = []
	(f, b) = (0, n - 1)
	while f <= b:
		(i, j) = (3 * f, 3 * b + 2)
		ans.append((i + 1, j + 1))
		f += 1
		b -= 1
	print(len(ans))
	for (u, v) in ans:
		print(u, v)
	return
for _ in range(int(input())):
	solve()


t = int(input())
import math
while t > 0:
	n = int(input())
	s = ''
	for _ in range(n):
		s += 'BAN'
	print(math.ceil(n / 2))
	i = 0
	j = len(s) - 1
	while i < j:
		print(i + 1, end=' ')
		print(j + 1)
		i += 3
		j -= 3
	t -= 1


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


t = int(input())
for _ in range(t):
	n = int(input())
	print((n + 1) // 2)
	left = 1
	right = 3 * n
	while left < right:
		print(left, right)
		left += 3
		right -= 3


from math import *

def solve():
	n = int(input())
	r = (n + 1) // 2
	print(r)
	for k in range(0, r):
		print(3 * k + 1, 3 * n - 3 * k)
t = int(input())
for i in range(t):
	solve()


import math
import collections
import bisect
import heapq
from collections import deque
from math import sqrt, ceil, floor

def inp_arr():
	return list(map(int, input().strip().split(' ')))

def inp_str_arr():
	return list(input().strip().split(' '))

def inp_str():
	return input()

def solve():
	(n,) = inp_arr()
	ans = (n + 1) // 2
	print(ans)
	frm = 1
	to = 3 * n
	while ans > 0:
		print(frm, to)
		frm += 3
		to = to - 3
		ans -= 1
(tt,) = inp_arr()
for t in range(tt):
	solve()


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
TC = readInt()
for tc in range(TC):
	n = readInt()
	swaps = math.ceil(n / 2)
	print(swaps)
	res = []
	for i in range(swaps):
		res.append(i * 3 + 1)
		res.append(i * -3 - 1 + 3 * n + 1)
	print(*res)


for _ in range(int(input())):
	n = int(input())
	m = -(-n // 2)
	print(m)
	a = 1
	b = 3 * n
	for _ in range(m):
		print(a, b)
		a += 3
		b -= 3


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


import sys, math
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	print(n // 2 + n % 2)
	x = n // 2 + n % 2
	l = 1
	r = 3 * n
	while l < r:
		print(l, r)
		l += 3
		r -= 3


import math as mt
for _ in range(int(input())):
	n = int(input())
	print(mt.ceil(n / 2))
	i = 1
	j = 3 * n
	while i < 3 * n / 2 and j > 3 * n / 2:
		print(i, j)
		i += 3
		j -= 3


N = int(input())
for _ in range(N):
	n = int(input())
	if n % 2 == 0:
		print(n // 2)
		p = n // 2
		for i in range(n // 2):
			print(f'{3 * i + 1} {3 * i + 3 + 3 * p}')
	else:
		print(n // 2 + 1)
		p = n // 2 + 1
		for i in range(n // 2):
			print(f'{3 * i + 1} {3 * i + 3 + 3 * p}')
		p = n // 2
		print(f'{3 * p + 1} {3 * p + 3}')


def fun(s):
	if s % 2 == 0:
		print(s // 2)
		for i in range(0, s // 2):
			print(3 * i + 1, '', 3 * s - 3 * i)
		return
	else:
		print(s // 2 + 1)
		for i in range(0, s // 2):
			print(3 * i + 1, '', 3 * s - 3 * i)
		print(3 * s // 2, '', 3 * s // 2 + 2)
t = int(input())
for k in range(t):
	n = int(input())
	fun(n)


for _ in range(int(input())):
	a = int(input())
	lis = []
	z = a // 2
	if a & 1:
		z += 1
	(i, j) = (0, a * 3 - 1)
	for k in range(z):
		lis.append([i + 1, j + 1])
		i += 3
		j -= 3
	print(z)
	for i in lis:
		print(*i)


t = int(input())
for i in range(1, t + 1):
	n = int(input())
	s = list('BAN' * n)
	m = len(s)
	(left, right) = (0, m - 1)
	print(n % 2 + n // 2)
	out = []
	while left < right:
		print(left + 1, right + 1)
		(s[left], s[right]) = (s[right], s[left])
		while left < right and s[left] != 'B':
			left += 1
		while left < right and s[right] != 'N':
			right -= 1


t = int(input())
while t:
	n = int(input())
	if n % 2 == 1:
		h = n // 2 + 1
	else:
		h = n // 2
	print(h)
	for i in range(h):
		print(i * 3 + 1, (n - i) * 3)
	t = t - 1


for tc in range(int(input())):
	n = int(input())
	s = 'BAN' * n
	a = 0
	b = 3 * n - 1
	if n == 1:
		t = 1
	elif n % 2 == 0:
		t = n // 2
	else:
		t = n // 2 + 1
	print(t)
	while t > 0:
		print(a + 1, b + 1)
		a += 3
		b -= 3
		t -= 1


s = int(input())
for i in range(s):
	a = int(input())
	ans = (a + 1) // 2
	print(ans)
	for j in range(ans):
		print(j * 3 + 1, a * 3 - j * 3)


import math
t = int(input())

def swap(i, j, b):
	l = list(b)
	(l[i], l[j]) = (l[j], l[i])
	return ''.join(l)
for test in range(t):
	n = int(input())
	m = math.ceil(n / 2)
	print(m)
	tmp1 = 1
	tmp2 = 3 * n
	for i in range(m):
		print(f'{tmp1} {tmp2}')
		tmp1 += 3
		tmp2 -= 3


for _ in range(int(input())):
	n = int(input())
	if n % 2 != 0:
		x = int((n + 1) / 2)
	else:
		x = int(n / 2)
	print(x)
	si = 1
	ei = 3 * n
	for i in range(x):
		print(si, ei)
		si += 3
		ei -= 3


for _ in range(int(input())):
	n = int(input())
	su = 3 * n + 1
	if n % 2 == 0:
		m = n // 2
		print(m)
		i = 1
		while m > 0:
			print(i, su - i)
			i += 3
			m -= 1
	else:
		m = (n + 1) // 2
		j = m
		print(m)
		i = 1
		while m > 1:
			print(i, su - i)
			i += 3
			m -= 1
		print((j - 1) * 3 + 1, (j - 1) * 3 + 3)


t = int(input())
for i in range(t):
	n = int(input())
	i = 0
	j = 3 * n - 1
	count = 0
	while i < j:
		count += 1
		i += 3
		j -= 3
	i = 0
	j = 3 * n - 1
	print(count)
	while i < j:
		print(i + 1, j + 1)
		i += 3
		j -= 3


for _ in range(int(input())):
	g = int(input())
	print((g + 1) // 2)
	for i in range(0, (g + 1) // 2):
		print(1 + i * 3, (g - i) * 3)