Salmon is playing a game!
He is given two integers $N$ and $K$. His goal is to output $K$ pairs $(x_i,y_i)$. He creates a function $f$ such that $f(x_i) = y_i$ and $f$ is undefined for all other values of $x$. His pairs must then meet the following conditions:
- All $x_i$ are distinct.
- All $y_i$ are distinct.
- All $x_i, y_i$ are in the range $[0,2^N - 1]$ and are integers.
- $f(f(x_i))$ is defined for all $i$.
- Let $H(x)$ be the number of set bits in the binary representation of $x$. Then, $H(x_i) \neq H(f(f(x_i)))$ for all $i$.
Unfortunately, Salmon is unable to solve this. Help Salmon win the game!

If there are multiple correct solutions, you may output any one of them. It can be proven that a solution exists for all $N$ and $K$ that meet constraints.

-----Input-----
- The first line input contains a single integer $T$ denoting the number of testcases
- Each of the next $T$ lines contains two space-separated integers $N$ and $K$ respectively.

-----Output-----
- Output $K$ lines for each testcase.
- The $i$-th line of a testcase should contain two space-separated integers: $x_i$ and $y_i$, following the given constraints.

-----Constraints-----
- $1 \leq T \leq 2^{15}$
- $3 \leq N \leq 18$ 
- $3 \leq K \leq 2^N$ 
- The sum of $2^N$ over all testcases doesn't exceed $2^{18}$

-----Subtasks-----
- Subtask 1 [20 points]: $K \leq 8$
- Subtask 2 [40 points]: $K = 2^N$
- Subtask 3 [40 points]: No additional constraints.

-----Sample Input-----
2
3 7
4 6

-----Sample Output-----
5 3
1 7
0 4
2 5
3 1
4 2 
7 0
1 10
10 14
15 1
14 13
5 15
13 5

-----Explanation-----
In the answer to the first testcase, there are 7 pairs. $x_i$ and $y_i$ are all in the range $[0,2^3 - 1]$, which is the range $[0,7]$. All values of $x_i$ are distinct, and all values of $y_i$ are distinct. However, note that some integers appear in both lists. For example, 5 appears both as $x_1$ and as $y_4$. This is allowed. For all $x_i$, $f(f(x_i))$ is defined and $H(f(f(x_i))) \neq H(x_i)$. For example, $f(f(7)) = 4$. $H(7) = 3$, but $H(4) = 1$. Therefore, $H(f(f(7))) \neq H(7)$, as desired.

Difficulty: UNKNOWN_DIFFICULTY

Starter code:

Solutions:
for _ in range(int(input())):
	(n, k) = [int(x) for x in input().split()]
	if k % 4 == 0:
		for i in range(0, k, 4):
			print(i, i + 1)
			print(i + 1, i + 2)
			print(i + 2, i + 3)
			print(i + 3, i)
	elif k % 4 == 1:
		for i in range(4, k - 1, 4):
			print(i, i + 1)
			print(i + 1, i + 2)
			print(i + 2, i + 3)
			print(i + 3, i)
		print(0, 1)
		print(1, 2)
		print(2, 3)
		print(3, (1 << n) - 1)
		print((1 << n) - 1, 0)
	elif k % 4 == 2:
		for i in range(4, k - 2, 4):
			print(i, i + 1)
			print(i + 1, i + 2)
			print(i + 2, i + 3)
			print(i + 3, i)
		print(0, 1)
		print(1, 2)
		print(2, 3)
		print(3, (1 << n) - 2)
		print((1 << n) - 2, (1 << n) - 1)
		print((1 << n) - 1, 0)
	elif k != 3:
		n = 1 << n
		n -= 1
		for i in range(4, k - 3, 4):
			print(i, i + 1)
			print(i + 1, i + 2)
			print(i + 2, i + 3)
			print(i + 3, i)
		print(2, 3)
		print(3, n - 1)
		print(n - 1, 0)
		print(0, 1)
		print(1, n - 2)
		print(n - 2, n)
		print(n, 2)
	else:
		print(0, 1)
		print(1, 3)
		print(3, 0)


import math
T = int(input())

def nb_bits(i, N):
	nb = 0
	for j in range(N):
		mask = 1 << j
		if i & mask == mask:
			nb += 1
	return nb
for t in range(T):
	(N, K) = map(int, input().strip().split(' '))
	d = {}
	for i in range(1, N + 1):
		d[i] = set()
	for i in range(2 ** N):
		nb = nb_bits(i, N)
		if nb != 0:
			d[nb].add(i)
	last = d[1].pop()
	first = last
	print(0, last)
	should_not_be = 0
	for i in range(K - 2):
		for j in range(1, N + 1):
			if len(d[j]) > 0 and j != should_not_be and (not (i == K - 3 and j == nb_bits(first, N))):
				n = d[j].pop()
				break
		print(last, n)
		should_not_be = nb_bits(last, N)
		last = n
	print(last, 0)


def num_bits(number):
	binary = bin(number)
	setBits = [ones for ones in binary[2:] if ones == '1']
	return len(setBits)
T = int(input())
for i in range(T):
	(N, K) = input().split(' ')
	N = int(N)
	K = int(K)
	l = []
	if K == 3:
		l = [0, 1, 3, 0]
	elif K == 4:
		l = [0, 1, 3, 7, 0]
	elif K == 5:
		l = [0, 1, 2, 3, 5, 0]
	elif K == 6:
		l = [0, 1, 2, 3, 5, 7, 0]
	elif K == 7:
		l = [1, 2, 3, 5, 4, 7, 0, 1]
	else:
		l = [1, 2, 3, 5, 4, 7, 0, 6, 1]
	for i in range(K):
		print(l[i], l[i + 1])


from os import path
import sys
from functools import cmp_to_key as ctk
from collections import deque, defaultdict as dd
from bisect import bisect, bisect_left, bisect_right, insort, insort_left, insort_right
from itertools import permutations
from datetime import datetime
from math import ceil, sqrt, log, gcd

def ii():
	return int(input())

def si():
	return input()

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

def li():
	return list(mi())
abc = 'abcdefghijklmnopqrstuvwxyz'
abd = {'a': 0, 'b': 1, 'c': 2, 'd': 3, 'e': 4, 'f': 5, 'g': 6, 'h': 7, 'i': 8, 'j': 9, 'k': 10, 'l': 11, 'm': 12, 'n': 13, 'o': 14, 'p': 15, 'q': 16, 'r': 17, 's': 18, 't': 19, 'u': 20, 'v': 21, 'w': 22, 'x': 23, 'y': 24, 'z': 25}
mod = 1000000007
inf = float('inf')
vow = ['a', 'e', 'i', 'o', 'u']
(dx, dy) = ([-1, 1, 0, 0], [0, 0, 1, -1])

def bo(i):
	return ord(i) - ord('a')

def solve():
	for _ in range(ii()):
		(n, k) = mi()
		if k == 3:
			print(1, 7)
			print(7, 3)
			print(3, 1)
		if k == 4:
			print(1, 7)
			print(7, 3)
			print(3, 6)
			print(6, 1)
		if k == 5:
			print(0, 1)
			print(1, 3)
			print(3, 5)
			print(5, 7)
			print(7, 0)
		if k == 6:
			print(0, 1)
			print(1, 2)
			print(2, 3)
			print(3, 5)
			print(5, 7)
			print(7, 0)
		if k == 7:
			print(5, 3)
			print(1, 7)
			print(0, 4)
			print(2, 5)
			print(3, 1)
			print(4, 2)
			print(7, 0)
		if k == 8:
			print(5, 6)
			print(0, 4)
			print(2, 5)
			print(3, 1)
			print(4, 2)
			print(1, 7)
			print(6, 0)
			print(7, 3)
			continue
		if k == pow(2, n):
			x = [[] for i in range(n + 1)]
			for i in range(1 << n):
				c = 0
				for j in range(n):
					if i >> j & 1:
						c += 1
				x[c].append(i)
			dq = deque([0])
			for i in range(n):
				a = x[i]
				b = x[i + 1]
				if len(a) <= len(b):
					for j in range(len(a)):
						print(a[j], b[j])
					for j in range(len(a), len(b)):
						dq.append(b[j])
				else:
					for j in range(len(b)):
						print(a[j], b[j])
					x2 = len(b)
					for j in range(len(b), len(a)):
						if len(dq) == 0:
							break
						x1 = dq[0]
						dq.popleft()
						print(a[j], x1)
						x2 += 1
					for j in range(x2, len(a)):
						dq.append(a[j])
			print(x[-1][0], dq[0])

def __starting_point():
	solve()
__starting_point()


from fractions import Fraction
import numpy as np
import sys, bisect, copyreg, statistics, os, time, socket, socketserver, atexit, io
from math import gcd, ceil, floor, sqrt, copysign, factorial, fmod, fsum, degrees
from math import expm1, exp, log, log2, acos, asin, cos, tan, sin, pi, e, tau, inf, nan, atan2
from collections import Counter, defaultdict, deque, OrderedDict
from itertools import combinations, permutations, accumulate, groupby, compress
from numpy.linalg import matrix_power as mp
from bisect import bisect_left, bisect_right, bisect, insort, insort_left, insort_right
from statistics import *
from copy import copy, deepcopy
from functools import reduce, cmp_to_key, lru_cache
from io import BytesIO, IOBase
from scipy.spatial import ConvexHull
from heapq import *
from decimal import *
from queue import Queue, PriorityQueue
from re import sub, subn
from random import shuffle, randrange, randint, random
from types import GeneratorType
from string import ascii_lowercase
from time import perf_counter
from datetime import datetime
from operator import ior, mul
if sys.version_info[0] < 3:
	from builtins import xrange as range
	from future_builtins import ascii, filter, hex, map, oct, zip

def graph(vertex):
	return [[] for i in range(vertex + 1)]

def lcm(a, b):
	return a * b // gcd(a, b)

def most_frequent(List):
	return Counter(List).most_common(1)[0][0]

def most_common(List):
	return mode(List)

def chinese_remainder(a, p):
	prod = reduce(op.mul, p, 1)
	x = [prod // piii for piii in p]
	return sum((a[i] * pow(x[i], p[i] - 2, p[i]) * x[i] for i in range(len(a)))) % prod

def bootstrap(f, stack=[]):

	def wrappedfunc(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		else:
			to = f(*args, **kwargs)
			while True:
				if type(to) is GeneratorType:
					stack.append(to)
					to = next(to)
				else:
					stack.pop()
					if not stack:
						break
					to = stack[-1].send(to)
			return to
	return wrappedfunc

def readTree():
	v = II()
	adj = [set() for i in range(v + 1)]
	for i in range(v - 1):
		(u1, u2) = MI()
		adj[u1].add(u2)
		adj[u2].add(u1)
	return (adj, v)

def setBit(n):
	return bin(n).count('1')

def digitsSum(n):
	return sum(list(map(int, str(n).strip())))

def ncr(n, r):
	r = min(r, n - r)
	numer = reduce(op.mul, list(range(n, n - r, -1)), 1)
	denom = reduce(op.mul, list(range(1, r + 1)), 1)
	return numer // denom

def factors(n):
	return list(set(reduce(list.__add__, ([i, n // i] for i in range(1, int(n ** 0.5) + 1) if n % i == 0))))

def prime_factors(n):
	(i, factors) = (2, [])
	while i * i <= n:
		if n % i:
			i += 1
		else:
			n //= i
			factors.append(i)
	if n > 1:
		factors.append(n)
	return set(factors)

def prefixSum(arr):
	for i in range(1, len(arr)):
		arr[i] = arr[i] + arr[i - 1]
	return arr

def binomial_coefficient(n, k):
	if 0 <= k <= n:
		ntok = 1
		ktok = 1
		for t in range(1, min(k, n - k) + 1):
			ntok *= n
			ktok *= t
			n -= 1
		return ntok // ktok
	else:
		return 0

def get_num_2_5(n):
	fives = 0
	while n > 0 and n % 5 == 0:
		n //= 5
		fives += 1
	return (power2(n), fives)

def shift(a, i, num):
	for _ in range(num):
		(a[i], a[i + 1], a[i + 2]) = (a[i + 2], a[i], a[i + 1])

def powerOfK(k, max):
	if k == 1:
		return [1]
	if k == -1:
		return [-1, 1]
	result = []
	n = 1
	while n <= max:
		result.append(n)
		n *= k
	return result

def getAngle(a, b, c):
	ang = degrees(atan2(c[1] - b[1], c[0] - b[0]) - atan2(a[1] - b[1], a[0] - b[0]))
	return ang + 360 if ang < 0 else ang

def getLength(a, b):
	return sqrt((a[0] - b[0]) ** 2 + (a[1] - b[1]) ** 2)

def kadane(a, size):
	max_so_far = curr_max = a[0]
	for i in range(1, size):
		curr_max = max(a[i], curr_max + a[i])
		max_so_far = max(max_so_far, curr_max)
	return max_so_far

def divisors(n):
	result = []
	for i in range(1, ceil(sqrt(n)) + 1):
		if n % i == 0:
			result.append(i)
			result.append(n / i)
	return list(set(result))

def equal(x, y):
	return abs(x - y) <= 1e-09

def sumtilln(n):
	return n * (n + 1) // 2

def isPrime(n):
	if n <= 1:
		return False
	if n <= 3:
		return True
	if n % 2 == 0 or n % 3 == 0:
		return False
	for i in range(5, ceil(sqrt(n)) + 1, 6):
		if n % i == 0 or n % (i + 2) == 0:
			return False
	return True

def isPowerOf2(x):
	return x and (not x & x - 1)

def power2(n):
	return len(str(bin(n & ~(n - 1))) - 1)

def sqsum(n):
	return n * (n + 1) * (2 * n + 1) // 6

def cusum(n):
	return sumn(n) ** 2

def pa(a):
	print(*a)

def printarrayasstring(a):
	print(*a, sep='')

def pm(a):
	for i in a:
		print(*i)

def pmasstring(a):
	for i in a:
		print(*i, sep='')

def print_case_iterable(case_num, iterable):
	print('Case #{}: {}'.format(case_num, ' '.join(map(str, iterable))))

def print_case_number(case_num, iterable):
	print('Case #{}: {}'.format(case_num, iterable))

def isPerfectSquare(n):
	return pow(floor(sqrt(n)), 2) == n

def nC2(n, m):
	return n * (n - 1) // 2 % m

def modInverse(n, p):
	return pow(n, p - 2, p)

def ncrmodp(n, r, p):
	num = den = 1
	for i in range(r):
		num = num * (n - i) % p
		den = den * (i + 1) % p
	return num * pow(den, p - 2, p) % p

def reverse(string):
	return ''.join(reversed(string))

def listtostr(s):
	return ' '.join([str(elem) for elem in s])

def binarySearch(arr, l, r, x):
	while l <= r:
		mid = l + (r - l) // 2
		if arr[mid] == x:
			return mid
		elif arr[mid] < x:
			l = mid + 1
		else:
			r = mid - 1
	return -1

def largestPower(n, p):
	x = 0
	while n:
		n //= p
		x += n
	return x

def isarrayodd(a):
	return len(a) == len(list(filter(lambda x: x % 2 == 1, a)))

def isarrayeven(a):
	return len(a) == len(list(filter(lambda x: x % 2 == 0, a)))

def isPalindrome(s):
	return s == s[::-1]

def gt(x, h, c, t):
	return (x * h + (x - 1) * c) / (2 * x - 1)

def CountFrequency(my_list):
	return Counter(my_list)

def CountFrequencyasPair(my_list1, my_list2, freq):
	for item in my_list1:
		freq[item][0] = freq[item][0] + 1 if item in freq else 1
	for item in my_list2:
		freq[item][1] = freq[item][1] + 1 if item in freq else 1
	return freq

def CountSquares(a, b):
	return floor(sqrt(b)) - ceil(sqrt(a)) + 1

def binarySearchCount(arr, n, key):
	left = 0
	right = n - 1
	count = 0
	while left <= right:
		mid = int((right + left) / 2)
		if arr[mid] <= key:
			(count, left) = (mid + 1, mid + 1)
		else:
			right = mid - 1
	return count

def primes(n):
	(sieve, l) = ([True] * (n + 1), [])
	for p in range(2, n + 1):
		if sieve[p]:
			l.append(p)
		for i in range(p, n + 1, p):
			sieve[i] = False
	return l

def Next_Greater_Element_for_all_in_array(arr):
	(s, n, reta, retb) = (list(), len(arr), [], [])
	arr1 = [list([0, i]) for i in range(n)]
	for i in range(n - 1, -1, -1):
		while len(s) > 0 and s[-1][0] <= arr[i]:
			s.pop()
		arr1[i][0] = -1 if len(s) == 0 else s[-1]
		s.append(list([arr[i], i]))
	for i in range(n):
		reta.append(list([arr[i], i]))
		retb.append(arr1[i][0])
	return (reta, retb)

def find_lcm_array(A):
	l = A[0]
	for i in range(1, len(A)):
		l = lcm(l, A[i])
	return l

def polygonArea(X, Y, n):
	area = 0.0
	j = n - 1
	for i in range(n):
		area += (X[j] + X[i]) * (Y[j] - Y[i])
		j = i
	return abs(area / 2.0)

def merge(a, b):
	return a | b

def subarrayBitwiseOR(A):
	(res, pre) = (set(), {0})
	for x in A:
		pre = {x | y for y in pre} | {x}
		res |= pre
	return len(res)

def subset_sum(numbers, l, target, partial=[]):
	s = sum(partial)
	if l <= s <= target:
		print('sum(%s)=%s' % (partial, s))
	if s >= target:
		return
	for i in range(len(numbers)):
		subset_sum(numbers[i + 1:], l, target, partial + [numbers[i]])

def isSubsetSum(arr, n, summ):
	subarr = [[False for i in range(summ + 1)] for i in range(n + 1)]
	for i in range(n + 1):
		subarr[i][0] = True
	for i in range(1, summ + 1):
		subarr[0][i] = False
	for i in range(1, n + 1):
		for j in range(1, summ + 1):
			if j < arr[i - 1]:
				subarr[i][j] = subarr[i - 1][j]
			if j >= arr[i - 1]:
				subarr[i][j] = subarr[i - 1][j] or subarr[i - 1][j - arr[i - 1]]
	return subarr[n][summ]

def pre(s):
	n = len(s)
	pi = [0] * n
	for i in range(1, n):
		j = pi[i - 1]
		while j and s[i] != s[j]:
			j = pi[j - 1]
		if s[i] == s[j]:
			j += 1
		pi[i] = j
	return pi

def prodofarray(a):
	return np.prod(a)

def binary(x, length=16):
	y = bin(x)[2:]
	return y if len(y) >= length else '0' * (length - len(y)) + y

def printSubsequences(arr, index, subarr):
	if index == len(arr):
		if len(subarr) != 0:
			print(subarr)
	else:
		printSubsequences(arr, index + 1, subarr)
		printSubsequences(arr, index + 1, subarr + [arr[index]])
	return

def modFact(n, p):
	if n >= p:
		return 0
	result = 1
	for i in range(1, n + 1):
		result = result * i % p
	return result

class LRUCache:

	def __init__(self, capacity: int):
		self.cache = OrderedDict()
		self.capacity = capacity

	def get(self, key: int) -> int:
		if key not in self.cache:
			return -1
		else:
			self.cache.move_to_end(key)
			return self.cache[key]

	def put(self, key: int, value: int) -> None:
		self.cache[key] = value
		self.cache.move_to_end(key)
		if len(self.cache) > self.capacity:
			self.cache.popitem(last=False)

class segtree:

	def __init__(self, n):
		self.m = 1
		while self.m < n:
			self.m *= 2
		self.data = [0] * (2 * self.m)

	def __setitem__(self, i, x):
		x = +(x != 1)
		i += self.m
		self.data[i] = x
		i >>= 1
		while i:
			self.data[i] = self.data[2 * i] + self.data[2 * i + 1]
			i >>= 1

	def __call__(self, l, r):
		l += self.m
		r += self.m
		s = 0
		while l < r:
			if l & 1:
				s += self.data[l]
				l += 1
			if r & 1:
				r -= 1
				s += self.data[r]
			l >>= 1
			r >>= 1
		return s

class FenwickTree:

	def __init__(self, n):
		self.n = n
		self.bit = [0] * (n + 1)

	def update(self, x, d):
		while x <= self.n:
			self.bit[x] += d
			x += x & -x

	def query(self, x):
		res = 0
		while x > 0:
			res += self.bit[x]
			x -= x & -x
		return res

	def range_query(self, l, r):
		return self.query(r) - self.query(l - 1)

class Graph:

	def __init__(self, V):
		self.V = V
		self.adj = [[] for i in range(V)]

	def DFSUtil(self, temp, v, visited):
		visited[v] = True
		temp.append(v)
		for i in self.adj[v]:
			if visited[i] == False:
				temp = self.DFSUtil(temp, i, visited)
		return temp

	def addEdge(self, v, w):
		self.adj[v].append(w)
		self.adj[w].append(v)

	def connectedComponents(self):
		(visited, cc) = ([False for i in range(self.V)], [])
		for v in range(self.V):
			if visited[v] == False:
				temp = []
				cc.append(self.DFSUtil(temp, v, visited))
		return cc

class MergeFind:

	def __init__(self, n):
		self.parent = list(range(n))
		self.size = [1] * n
		self.num_sets = n
		self.lista = [[_] for _ in range(n)]

	def find(self, a):
		to_update = []
		while a != self.parent[a]:
			to_update.append(a)
			a = self.parent[a]
		for b in to_update:
			self.parent[b] = a
		return self.parent[a]

	def merge(self, a, b):
		a = self.find(a)
		b = self.find(b)
		if a == b:
			return
		if self.size[a] < self.size[b]:
			(a, b) = (b, a)
		self.num_sets -= 1
		self.parent[b] = a
		self.size[a] += self.size[b]
		self.lista[a] += self.lista[b]
		self.lista[b] = []

	def set_size(self, a):
		return self.size[self.find(a)]

	def __len__(self):
		return self.num_sets
if os.path.exists('in.txt'):
	sys.stdin = open('in.txt', 'r')
if os.path.exists('out.txt'):
	sys.stdout = open('out.txt', 'w')

def inp():
	return sys.stdin.readline()

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

def I():
	return inp()

def II():
	return int(inp())

def FI():
	return float(inp())

def SI():
	return list(str(inp()))

def MI():
	return map(int, inp().split())

def LI():
	return list(MI())

def SLI():
	return sorted(LI())

def MF():
	return map(float, inp().split())

def LF():
	return list(MF())

def SLF():
	return sorted(LF())
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 998244353
mod = 10 ** 9 + 7

def __starting_point():
	k_max = 524288
	digmap = defaultdict(list)
	for i in range(k_max):
		digmap[bin(i).count('1')].append(i)
	for _ in range(II()):
		(n, k) = MI()
		seq_max = (1 << n) - 1
		seq = [None] * k
		odd_pointer = 0
		odd_position = 1
		even_pointer = 0
		even_position = 0
		idx = 0
		current_flag = False
		while idx < k:
			if current_flag:
				seq[idx] = digmap[odd_position][odd_pointer]
				odd_pointer += 1
				if odd_pointer >= len(digmap[odd_position]):
					odd_position += 2
					odd_pointer = 0
				if digmap[odd_position][odd_pointer] > seq_max:
					odd_position += 2
					odd_pointer = 0
				idx += 1
			else:
				seq[idx] = digmap[even_position][even_pointer]
				even_pointer += 1
				if even_pointer >= len(digmap[even_position]):
					even_position += 2
					even_pointer = 0
				if digmap[even_position][even_pointer] > seq_max:
					even_position += 2
					even_pointer = 0
				idx += 1
			if idx & 1:
				current_flag = not current_flag
		if bin(seq[1]).count('1') == bin(seq[k - 1]).count('1'):
			seq[k - 1] = seq_max
		if bin(seq[1]).count('1') == bin(seq[k - 1]).count('1'):
			seq[k - 1] = seq_max
		for idx in range(k - 1):
			print(seq[idx], seq[idx + 1])
		print(seq[k - 1], seq[0])
__starting_point()