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.

```python

USER_FILENAME = "<user_code>"
import sys, json, builtins
import math, heapq, bisect, itertools, functools, collections, statistics, fractions, decimal, operator, array, random, re, string, os, pathlib
try:
    import resource as _res
except Exception:
    _res = None
from collections import Counter, defaultdict, deque, OrderedDict
from functools import lru_cache, reduce
from itertools import accumulate, permutations, combinations, product
from math import gcd, ceil, floor, sqrt
from decimal import Decimal
try:
    from typing import *
except Exception:
    pass
try:
    sys.setrecursionlimit(1_000_000)
except Exception:
    pass
try:
    import site as _site
    try:
        _sys_sites = _site.getsitepackages() if hasattr(_site, "getsitepackages") else []
        for _p in _sys_sites:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
    try:
        _usp = _site.getusersitepackages()
        if isinstance(_usp, str):
            _usp = [_usp]
        for _p in _usp:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
except Exception:
    pass

ns = {"__name__": "__main__"}
for _k, _v in list(globals().items()):
    if not _k.startswith("_"):
        ns[_k] = _v
_CODE = '# import all important libraries and inbuilt functions\n\nfrom fractions import Fraction\nimport numpy as np\nimport sys,bisect,copyreg,statistics,os,time,socket,socketserver,atexit,io\nfrom math import gcd,ceil,floor,sqrt,copysign,factorial,fmod,fsum,degrees\nfrom math import expm1,exp,log,log2,acos,asin,cos,tan,sin,pi,e,tau,inf,nan,atan2\nfrom collections import Counter,defaultdict,deque,OrderedDict   \nfrom itertools import combinations,permutations,accumulate,groupby,compress \nfrom numpy.linalg import matrix_power as mp\nfrom bisect import bisect_left,bisect_right,bisect,insort,insort_left,insort_right\nfrom statistics import *\nfrom copy import copy,deepcopy\nfrom functools import reduce,cmp_to_key,lru_cache\nfrom io import BytesIO, IOBase\nfrom scipy.spatial import ConvexHull\nfrom heapq import *\nfrom decimal import *\nfrom queue import Queue,PriorityQueue\nfrom re import sub,subn\nfrom random import shuffle,randrange,randint,random\nfrom types import GeneratorType \nfrom string import ascii_lowercase\nfrom time import perf_counter\nfrom datetime import datetime\nfrom operator import ior,mul\n\n# never import pow from math library it does not perform modulo\n# use standard pow -- better than math.pow\n\n# end of library import\n\n# map system version faults\nif sys.version_info[0] < 3:\n    from builtins import xrange as range\n    from future_builtins import ascii, filter, hex, map, oct, zip\n\n# template of many functions used in competitive programming can add more later \n# based on need we will use this commonly.\n\n# definition of vertex of a graph\ndef graph(vertex):  return [[] for i in range(vertex+1)]\n\ndef lcm(a,b):   return (a*b)//gcd(a,b)\n\n# most common list in a array of lists\ndef most_frequent(List):    return Counter(List).most_common(1)[0][0]\n\n# element with highest frequency\ndef most_common(List):    return(mode(List))\n\n#In number theory, the Chinese remainder theorem states that \n#if one knows the remainders of the Euclidean division of an integer n by \n#several integers, then one can determine uniquely the remainder of the \n#division of n by the product of these integers, under the condition \n#that the divisors are pairwise coprime.\ndef chinese_remainder(a, p):\n    prod = reduce(op.mul, p, 1)\n    x = [prod // piii for piii in p]\n    return sum(a[i] * pow(x[i], p[i] - 2, p[i]) * x[i] for i in range(len(a))) % prod\n\ndef bootstrap(f, stack=[]):\n    def wrappedfunc(*args, **kwargs):\n        if stack:            \n            return f(*args, **kwargs)\n        else:\n            to = f(*args, **kwargs)\n            while True:\n                if type(to) is GeneratorType:\n                    stack.append(to);to = next(to)\n                else:\n                    stack.pop()\n                    if not stack:  \n                        break\n                    to = stack[-1].send(to)\n            return to \n    return wrappedfunc\n\n# input for a binary tree\ndef readTree(): \n    v = II()\n    adj=[set() for i in range(v+1)]\n    for i in range(v-1):\n        u1,u2 = MI()\n        adj[u1].add(u2)\n        adj[u2].add(u1)\n    return adj,v\n\n#count setbits of a number.\ndef setBit(n):  return bin(n).count(\'1\'); \n\n# sum of digits of a number\ndef digitsSum(n):    return sum(list(map(int, str(n).strip()))) \n\n# ncr efficiently\ndef ncr(n, r):\n    r = min(r, n - r)\n    numer = reduce(op.mul, list(range(n, n - r, -1)), 1)\n    denom = reduce(op.mul, list(range(1, r + 1)), 1)\n    return numer // denom  # or / in Python 2\n\n#factors of a number\ndef 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))))\n\n#prime factors of a number\ndef prime_factors(n):\n    i,factors = 2,[]\n    while i * i <= n:\n        if n % i:\n            i += 1\n        else:\n            n //= i\n            factors.append(i)\n    if n > 1:   factors.append(n)\n    return set(factors)\n\ndef prefixSum(arr):\n    for i in range(1, len(arr)):\n        arr[i] = arr[i] + arr[i-1]\n    return arr    \n\ndef binomial_coefficient(n, k):\n    if 0 <= k <= n:\n        ntok = 1\n        ktok = 1\n        for t in range(1, min(k, n - k) + 1):\n            ntok *= n\n            ktok *= t\n            n -= 1\n        return ntok // ktok\n    else:\n        return 0\n\ndef get_num_2_5(n):\n    fives = 0\n    while n>0 and n%5 == 0:\n        n//=5\n        fives+=1\n    return (power2(n),fives)\n\ndef shift(a,i,num):\n\tfor _ in range(num):        a[i],a[i+1],a[i+2] = a[i+2],a[i],a[i+1] \n\ndef powerOfK(k, max):\n    if k == 1:\n        return [1]\n    if k == -1:\n        return [-1, 1] \n    result = []\n    n = 1\n    while n <= max:\n        result.append(n)\n        n *= k\n    return result\n\ndef getAngle(a, b, c):\n\tang = degrees(atan2(c[1]-b[1], c[0]-b[0]) - atan2(a[1]-b[1], a[0]-b[0]))\n\treturn ang + 360 if ang < 0 else ang\n\ndef getLength(a,b):    return sqrt((a[0]-b[0])**2 + (a[1]-b[1])**2)\n\n# maximum subarray sum use kadane\'s algorithm\ndef kadane(a,size):\n    max_so_far = curr_max = a[0]       \n    for i in range(1,size): \n        curr_max = max(a[i], curr_max + a[i]) \n        max_so_far = max(max_so_far,curr_max)           \n    return max_so_far \n\ndef divisors(n):\n    result = []\n    for i in range(1,ceil(sqrt(n))+1):\n        if n%i == 0:\n            result.append(i)\n            result.append(n/i)\n    return list(set(result))\n\ndef equal(x,y):     return abs(x-y) <= 1e-9\n\ndef sumtilln(n):      return ((n*(n+1))//2)\n\ndef isPrime(n) : \n    if (n <= 1) :\n        return False\n    if (n <= 3) :\n        return True\n    if (n % 2 == 0 or n % 3 == 0) :\n        return False\n    for i in range(5,ceil(sqrt(n))+1,6):\n        if (n % i == 0 or n % (i + 2) == 0) :      \n            return False\n    return True\n\ndef isPowerOf2(x): return (x and (not(x & (x - 1))) )\n\ndef power2(n):    return len(str(bin((n & (~(n - 1)))))-1)\n\ndef sqsum(n):    return ((n*(n+1))*(2*n+1)//6)\n\ndef cusum(n):    return ((sumn(n))**2)\n\ndef pa(a):    print(*a)\n\ndef printarrayasstring(a):    print(*a,sep = \'\')\n\ndef pm(a):\n    for i in a: print(*i)\n\ndef pmasstring(a):\n    for i in a: print(*i,sep = \'\')\n\ndef print_case_iterable(case_num, iterable):    print("Case #{}: {}".format(case_num," ".join(map(str,iterable))))\n\ndef print_case_number(case_num, iterable):    print("Case #{}: {}".format(case_num,iterable))\n\ndef isPerfectSquare(n):    return pow(floor(sqrt(n)),2) == n\n\ndef nC2(n,m):    return (((n*(n-1))//2) % m)\n\ndef modInverse(n,p):    return pow(n,p-2,p)\n\ndef ncrmodp(n, r, p):  \n    num = den = 1\n    for i in range(r):\n        num = (num * (n - i)) % p \n        den = (den * (i + 1)) % p \n    return (num * pow(den,p - 2, p)) % p \n\ndef reverse(string):    return "".join(reversed(string))        \n\ndef listtostr(s):    return \' \'.join([str(elem) for elem in s]) \n\ndef binarySearch(arr, l, r, x): \n    while l <= r: \n        mid = l + (r - l) // 2; \n        if arr[mid] == x:\n            return mid \n        elif arr[mid] < x:\n            l = mid + 1\n        else:\n            r = mid - 1\n    return -1\n\n# Returns largest power of p that divides n!  \ndef largestPower(n, p): \n    x = 0\n    while (n): \n        n //= p \n        x += n  \n    return x  \n\ndef isarrayodd(a):  return len(a) == len(list(filter(lambda x: (x%2 == 1) , a))) \n\ndef isarrayeven(a): return len(a) == len(list(filter(lambda x: (x%2 == 0) , a))) \n\ndef isPalindrome(s):    return s == s[::-1] \n\ndef gt(x,h,c,t):    return ((x*h+(x-1)*c)/(2*x-1))\n\ndef CountFrequency(my_list):    return Counter(my_list)\n\ndef CountFrequencyasPair(my_list1,my_list2,freq): \n    for item in my_list1:\n        freq[item][0] = (freq[item][0] + 1 if (item in freq) else 1)\n    for item in my_list2:\n        freq[item][1] = (freq[item][1] + 1 if (item in freq) else 1)     \n    return freq \n\ndef CountSquares(a, b):return (floor(sqrt(b)) - ceil(sqrt(a)) + 1) \n\ndef binarySearchCount(arr, n, key):   \n    left = 0\n    right = n - 1\n    count = 0  \n    while (left <= right):  \n        mid = int((right + left) / 2) \n        if (arr[mid] <= key):\n            count,left = mid + 1,mid + 1\n        else:\n            right = mid - 1      \n    return count\n\ndef primes(n):\n    sieve,l = [True] * (n+1),[]\n    for p in range(2, n+1):\n        if (sieve[p]):\n            l.append(p)\n        for i in range(p, n+1, p):\n            sieve[i] = False\n    return l\n\ndef Next_Greater_Element_for_all_in_array(arr): \n    s,n,reta,retb = list(),len(arr),[],[]\n    arr1 = [list([0,i]) for i in range(n)]\n    for i in range(n - 1, -1, -1): \n        while (len(s) > 0 and s[-1][0] <= arr[i]):\n            s.pop() \n        arr1[i][0] = (-1 if len(s) == 0 else s[-1])\n        s.append(list([arr[i],i]))\t\t\n    for i in range(n):\n        reta.append(list([arr[i],i]))\n        retb.append(arr1[i][0])\n    return reta,retb\n\ndef find_lcm_array(A):\n    l = A[0] \n    for i in range(1, len(A)):\n        l = lcm(l, A[i]) \n    return l\n\ndef polygonArea(X,Y,n):   \n    area = 0.0\n    j = n - 1\n    for i in range(n):\n        area += (X[j] + X[i]) * (Y[j] - Y[i])\n        j = i   \n    return abs(area / 2.0)\n    \ndef merge(a, b):    return a|b \n\ndef subarrayBitwiseOR(A): \n    res,pre = set(),{0}\n    for x in A: \n        pre = {x | y for y in pre} | {x} \n        res |= pre \n    return len(res) \n\n# Print the all possible subset sums that lie in a particular interval of l <= sum <= target\ndef subset_sum(numbers,l,target, partial=[]):\n    s = sum(partial)\n    if l <= s <= target:\n        print("sum(%s)=%s" % (partial, s))\n    if s >= target:\n        return \n    for i in range(len(numbers)):\n        subset_sum(numbers[i+1:], l,target, partial + [numbers[i]])\n\ndef isSubsetSum(arr, n, summ):       \n    # The value of subarr[i][j] will be true if there is a \n    # subarr of arr[0..j-1] with summ equal to i \n    subarr = ([[False for i in range(summ + 1)] for i in range(n + 1)]) \n    \n    # If summ is 0, then answer is true  \n    for i in range(n + 1):\n        subarr[i][0] = True\n    \n    # If summ is not 0 and arr is empty,then answer is false  \n    for i in range(1, summ + 1):\n        subarr[0][i]= False\n    \n    # Fill the subarr table in botton up manner \n    for i in range(1, n + 1): \n        for j in range(1, summ + 1): \n            if j<arr[i-1]:\n                subarr[i][j] = subarr[i-1][j] \n            if j>= arr[i-1]:\n                subarr[i][j] = (subarr[i-1][j] or subarr[i - 1][j-arr[i-1]])       \n    return subarr[n][summ] \n\ndef pre(s):\n    n = len(s)\n    pi = [0] * n\n    for i in range(1, n):\n        j = pi[i - 1]\n        while j and s[i] != s[j]:    \n            j = pi[j - 1]\n        if s[i] == s[j]:\n            j += 1\n        pi[i] = j\n    return pi\n\ndef prodofarray(a):    return np.prod(a)\n\ndef binary(x, length=16):\n    y = bin(x)[2:]\n    return y if len(y) >= length else "0" * (length - len(y)) + y\n\ndef printSubsequences(arr, index, subarr): \n    if index == len(arr): \n        if len(subarr) != 0:\n            print(subarr)       \n    else:\n        printSubsequences(arr, index + 1, subarr)\n        printSubsequences(arr, index + 1, subarr+[arr[index]])       \n    return\n\ndef modFact(n, p): \n    if n >= p:\n        return 0      \n    result = 1\n    for i in range(1, n + 1):\n        result = (result * i) % p    \n    return result \n\n#defining a LRU Cache\n# where we can set values and get values based on our requirement\nclass LRUCache: \n\t# initialising capacity \n    def __init__(self, capacity: int): \n        self.cache = OrderedDict() \n        self.capacity = capacity\n        \n\t# we return the value of the key \n\t# that is queried in O(1) and return -1 if we \n\t# don\'t find the key in out dict / cache. \n\t# And also move the key to the end \n\t# to show that it was recently used.        \n    def get(self, key: int) -> int: \n        if key not in self.cache:\n            return -1\n        else:\n            self.cache.move_to_end(key)\n            return self.cache[key] \n        \n    def put(self, key: int, value: int) -> None: \n        self.cache[key] = value\n        self.cache.move_to_end(key) \n        if len(self.cache) > self.capacity:\n            self.cache.popitem(last = False)\n\nclass segtree:\n\n    def __init__(self,n):\n        self.m = 1\n        while self.m < n:\n            self.m *= 2\n        self.data = [0] * (2 * self.m)\n\n    def __setitem__(self,i,x):\n        x = +(x != 1)\n        i += self.m\n        self.data[i] = x\n        i >>= 1\n        while i:\n            self.data[i] = self.data[2 * i] + self.data[2 * i + 1]\n            i >>= 1\n\n    def __call__(self,l,r):\n        l += self.m\n        r += self.m\n        s = 0\n        while l < r:\n            if l & 1:\n                s += self.data[l]\n                l += 1\n            if r & 1:\n                r -= 1\n                s += self.data[r]\n            l >>= 1\n            r >>= 1\n        return s        \n\nclass FenwickTree:\n\n    def __init__(self, n):\n        self.n = n\n        self.bit = [0]*(n+1)  \n\n    def update(self, x, d):\n        while x <= self.n:\n            self.bit[x] += d\n            x += (x & (-x))  \n\n    def query(self, x):\n        res = 0\n        while x > 0:\n            res += self.bit[x]\n            x -= (x & (-x))\n        return res\n\n    def range_query(self, l, r):\n        return self.query(r) - self.query(l-1)    \n\n# Python program to print connected \n# components in an undirected graph \n\nclass Graph: \n    \n    def __init__(self,V):\n        self.V = V \n        self.adj = [[] for i in range(V)] \n        \n    def DFSUtil(self, temp, v, visited): \n        visited[v] = True\n        temp.append(v) \n        for i in self.adj[v]: \n            if visited[i] == False:\n                temp = self.DFSUtil(temp, i, visited) \n        return temp \n    \n    # method to add an undirected edge \n    def addEdge(self, v, w):\n        self.adj[v].append(w)\n        self.adj[w].append(v) \t\n        \n    # Method to retrieve connected components in an undirected graph\n    def connectedComponents(self): \n        visited,cc = [False for i in range(self.V)],[]\n        for v in range(self.V): \n            if visited[v] == False:\n                temp = []\n                cc.append(self.DFSUtil(temp, v, visited)) \n        return cc \n\nclass MergeFind:\n\n    def __init__(self, n):\n        self.parent = list(range(n))\n        self.size = [1] * n\n        self.num_sets = n\n        self.lista = [[_] for _ in range(n)]\n\n    def find(self, a):\n        to_update = []\n        while a != self.parent[a]:\n            to_update.append(a)\n            a = self.parent[a]\n        for b in to_update:\n            self.parent[b] = a\n        return self.parent[a]\n\n    def merge(self, a, b):\n        a = self.find(a)\n        b = self.find(b)\n        if a == b:\n            return\n        if self.size[a] < self.size[b]:\n            a, b = b, a\n        self.num_sets -= 1\n        self.parent[b] = a\n        self.size[a] += self.size[b]\n        self.lista[a] += self.lista[b]\n        self.lista[b] = []\n\n    def set_size(self, a):\n        return self.size[self.find(a)]\n\n    def __len__(self):\n        return self.num_sets\n\n# This is Kosaraju\'s Algorithm and use this class of graph for only that purpose    \n# can add more template functions here\n\n# end of template functions\n\n# To enable the file I/O i the below 2 lines are uncommented.\n\n# read from in.txt if uncommented\n\nif os.path.exists(\'in.txt\'):    sys.stdin = open(\'in.txt\',\'r\')\n\n# will print on Console if file I/O is not activated\n\nif os.path.exists(\'out.txt\'):     sys.stdout=open(\'out.txt\', \'w\')\n\n# inputs template\n\n#for fast input we are using sys.stdin\ndef inp(): return sys.stdin.readline()\n\n#for fast output, always take string\ndef out(var):     sys.stdout.write(str(var) + "\\n")  \n\n# custom base input needed for the program\ndef I():    return (inp())\ndef II():    return (int(inp()))\ndef FI():    return (float(inp()))\ndef SI():    return (list(str(inp())))\ndef MI():    return (map(int,inp().split()))\ndef LI():    return (list(MI()))\ndef SLI():    return (sorted(LI()))\ndef MF():    return (map(float,inp().split()))\ndef LF():    return (list(MF()))\ndef SLF():    return (sorted(LF()))\n\n# end of inputs template\n\n# common modulo values used in competitive programming\nsys.setrecursionlimit(10**9)\nINF = float(\'inf\')\nMOD = 998244353\nmod = 10**9+7\n\n# any particular user-defined functions for the code.\n# can be written here.   \n          \n# end of any user-defined functions\n\n# main functions for execution of the program.\ndef __starting_point():  \n    # execute your program from here.\n    # start your main code from here\n        \n    # Write your code   \n    k_max = 524288;digmap = defaultdict(list)    \n    for i in range(k_max):digmap[bin(i).count("1")].append(i)    \n    for _ in range(II()):\n      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\n      while idx < k:\n          if current_flag:\n              seq[idx] = digmap[odd_position][odd_pointer];odd_pointer += 1\n              if odd_pointer >= len(digmap[odd_position]):odd_position += 2;odd_pointer = 0\n              if digmap[odd_position][odd_pointer] > seq_max:odd_position += 2;odd_pointer = 0\n              idx += 1\n          else:\n              seq[idx] = digmap[even_position][even_pointer];even_pointer += 1\n              if even_pointer >= len(digmap[even_position]):even_position += 2;even_pointer = 0\n              if digmap[even_position][even_pointer] > seq_max:even_position += 2;even_pointer = 0\n              idx += 1\n          if idx & 1:current_flag = not current_flag      \n      if (bin(seq[1]).count("1") ==  bin(seq[k-1]).count("1")):        seq[k-1] = seq_max    \n      if (bin(seq[1]).count("1") ==  bin(seq[k-1]).count("1")):        seq[k-1] = seq_max    \n      for idx in range(k-1):        print(seq[idx], seq[idx+1])\n      print(seq[k-1], seq[0])\n            \n    # end of main code\n    # end of program\n\n# This program is written by :\n#   Shubham Gupta\n#   B.Tech (2019-2023)\n#   Computer Science and Engineering,\n#   Department of EECS\n#   Contact No:8431624358\n#   Indian Institute of Technology(IIT),Bhilai\n#   Sejbahar,\n#   Datrenga,\n#   Raipur,\n#   Chhattisgarh\n#   492015\n\n#   THANK YOU FOR \n#YOUR KIND PATIENCE FOR READING THE PROGRAM.    \n__starting_point()'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: