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 = 'def num_bits(number):\n    binary = bin(number)\n    setBits = [ones for ones in binary[2:] if ones==\'1\']\n    return len(setBits)\n\n# def test(l):\n#     for i in range(len(l)):\n#         if num_bits(l[i%size]) == num_bits(l[i+2]):\n#             print(l[i])\n#             return "FAILED"\n#     return "PASSED"\n# print(test([0,1,3]))\n# print(test([0,1,3,7]))\n# print(test([0,1,2,3,5]))\n# print(test([0,1,2,3,5,7]))\n# print(test([1,2,3,5,4,7,0]))\n# print(test([1,2,3,5,4,7,0,6]))\nT = int(input())\nfor i in range(T):\n    N,K = input().split(\' \')\n    N = int(N)\n    K = int(K)\n    l = []\n    if K==3:\n        l=[0,1,3,0]\n    elif K==4:\n        l=[0,1,3,7,0]\n    elif K==5:\n        l=[0,1,2,3,5,0]\n    elif K==6:\n        l=[0,1,2,3,5,7,0]\n    elif K==7:\n        l=[1,2,3,5,4,7,0,1]\n    else:\n        l = [1,2,3,5,4,7,0,6,1]\n\n    for i in range(K):\n        print(l[i],l[i+1])\n\n\n\n\'\'\'\n0,1,2,3,4,5,6,7\n0: 0\n1: 1,2,4,8\n2: 3,5,6,9,10,12\n3: 7,11,13,14\n4: 15\n\nK=3\n0 1 3 5 4 2 6 7\n0 1 3\nK=4\n0 1 3 7\nK=5\n0 1 3 7 2\nK=6\n0 1 3 7 2 5\nK=7\n0 1 3 7 2 5 \n\'\'\''
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 13275