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 = '\'\'\'\r\n    Auther: ghoshashis545 Ashis Ghosh\r\n    College: jalpaiguri Govt Enggineering College\r\n\r\n\'\'\'\r\nfrom os import path\r\nimport sys\r\nfrom functools import cmp_to_key as ctk\r\nfrom collections import deque,defaultdict as dd \r\nfrom bisect import bisect,bisect_left,bisect_right,insort,insort_left,insort_right\r\nfrom itertools import permutations\r\nfrom datetime import datetime\r\nfrom math import ceil,sqrt,log,gcd\r\ndef ii():return int(input())\r\ndef si():return input()\r\ndef mi():return map(int,input().split())\r\ndef li():return list(mi())\r\nabc=\'abcdefghijklmnopqrstuvwxyz\'\r\nabd={\'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}\r\nmod=1000000007\r\n#mod=998244353\r\ninf = float("inf")\r\nvow=[\'a\',\'e\',\'i\',\'o\',\'u\']\r\ndx,dy=[-1,1,0,0],[0,0,1,-1]\r\n\r\ndef bo(i):\r\n    return ord(i)-ord(\'a\')\r\n\r\n\r\ndef solve():\r\n    \r\n    for _ in range(ii()):\r\n        \r\n        n,k = mi()\r\n        if k==3:\r\n            print(1,7)\r\n            print(7,3)\r\n            print(3,1)\r\n        if k==4:\r\n            print(1,7)\r\n            print(7,3)\r\n            print(3,6)\r\n            print(6,1)\r\n        if k==5:\r\n            print(0,1)\r\n            print(1,3)\r\n            print(3,5)\r\n            print(5,7)\r\n            print(7,0)\r\n        if k==6:\r\n            print(0,1)\r\n            print(1,2)\r\n            print(2,3)\r\n            print(3,5)\r\n            print(5,7)\r\n            print(7,0)\r\n        if k==7:\r\n            print(5,3)\r\n            print(1,7)\r\n            print(0,4)\r\n            print(2,5)\r\n            print(3,1)\r\n            print(4,2)\r\n            print(7,0)\r\n        if k==8:\r\n            print(5,6)\r\n            print(0,4)\r\n            print(2,5)\r\n            print(3,1)\r\n            print(4,2)\r\n            print(1,7)\r\n            print(6,0)\r\n            print(7,3)\r\n            continue\r\n        if k == pow(2,n):\r\n            x = [[] for i in range(n+1)]\r\n            for i in range(1<<n):\r\n                c = 0\r\n                for j in range(n):\r\n                    if(i>>j)&1:\r\n                        c+=1\r\n                x[c].append(i)\r\n            \r\n            dq = deque([0])\r\n            for i in range(n):\r\n                a = x[i]\r\n                b = x[i+1]\r\n                if len(a) <= len(b):\r\n                    for j in range(len(a)):\r\n                        print(a[j],b[j])\r\n                    for j in range(len(a),len(b)):\r\n                        dq.append(b[j])\r\n                else:\r\n                    for j in range(len(b)):\r\n                        print(a[j],b[j])\r\n                    x2 = len(b)\r\n                    for j in range(len(b),len(a)):\r\n                        if len(dq)==0:\r\n                            break\r\n                        x1 = dq[0]\r\n                        dq.popleft()\r\n                        print(a[j],x1)\r\n                        x2+=1\r\n                    for j in range(x2,len(a)):\r\n                        dq.append(a[j])\r\n            print(x[-1][0],dq[0])\r\n\r\n            \r\n            \r\n        \r\n    \r\n    \r\n    \r\n    \r\n    \r\n    \r\n    \r\n    \r\n    \r\n    \r\n    \r\n    \r\n    \r\n    \r\n    \r\n    \r\n    \r\n    \r\n    \r\n    \r\n    \r\n    \r\n        \r\n        \r\n        \r\n        \r\ndef __starting_point():\r\n    solve()\r\n\n__starting_point()'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 366745