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 = '# cook your dish here\r\nimport math\r\n\r\nT = int(input())\r\n\r\ndef nb_bits(i, N):\r\n    nb = 0\r\n    for j in range(N):\r\n        mask = 1 << j\r\n        if i & mask == mask:\r\n            nb+=1\r\n    return nb\r\n            \r\n\r\nfor t in range(T):\r\n    N, K = map(int, input().strip().split(" "))\r\n    d = {}\r\n    for i in range(1, N+1):\r\n        d[i] = set()\r\n    for i in range(2**N):\r\n        nb = nb_bits(i, N)\r\n        if nb != 0:\r\n            d[nb].add(i)\r\n    \r\n    last = d[1].pop()\r\n    first = last\r\n    print(0, last)\r\n    should_not_be = 0\r\n    for i in range(K-2):\r\n        for j in range(1, N+1):\r\n            if len(d[j]) > 0 and j!=should_not_be and not (i == K-3 and j == nb_bits(first, N)):\r\n                n = d[j].pop()\r\n                break\r\n        print(last, n)\r\n        should_not_be = nb_bits(last, N)\r\n        last = n\r\n    print(last, 0)\r\n    '
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 13523