一家电话公司想要在城市中建立一个新的电话网络。该公司的目标是让城市中的每个人都能够互相通话。当然，在每对人之间建立直接连接是不可能的。相反，该公司使用一个由多个层组成的网络。

我们用 $S(j)$ 表示第 $j$ 层的网络交换机。一个交换机 $S(0)$ 由一个输入、一个输出和一条连接输入与输出的电缆组成。一个 $j > 0$ 的交换机 $S(j)$ 由 $2^j$ 个输入、$2^j$ 个输出和两个交换机 $S(j - 1)$ 组成。$S(j)$ 的输入 $i$ ($0 \le i < 2^j$) 通过电缆连接到两个 $S(j - 1)$ 交换机中每一个的输入 $i \bmod 2^{j-1}$。类似地，$S(j)$ 的输出 $i$ 连接到两个 $S(j - 1)$ 交换机中每一个的输出 $i \bmod 2^{j-1}$。

交换机 $S(j)$ 与其组成的两个交换机 $S(j - 1)$ 之间的连接方式。

我们考虑一个最外层包含一个交换机 $S(n)$ 的网络。可以证明，交换机 $S(n)$ 的任何输入和输出到任何一个 $S(0)$ 交换机都有一条唯一的连接路径。因此，$S(n)$ 的任何输入都可以连接到其任何输出，并且连接路径通过指定连接是由哪个 $S(0)$ 交换机建立的而唯一确定。

我们将属于交换机 $S(n)$ 的 $S(0)$ 交换机从 $0$ 到 $2^n - 1$ 进行编号。第 $i$ 个交换机 $S(0)$ 的定义如下：将数字 $i$ 写成二进制形式 $b_{n-1}b_{n-2} \dots b_0$。这通过以下步骤定义了从 $S(n)$ 的输入到第 $i$ 个交换机 $S(0)$ 的路径：对于每个 $j$，$b_j = 0$ 表示路径从 $S(j + 1)$ 延伸到与其直接连接的第一个 $S(j)$ 交换机，而 $b_j = 1$ 表示路径延伸到第二个 $S(j)$ 交换机。注意，无论选择 $S(n)$ 的哪个输入，该路径都会到达同一个 $S(0)$ 交换机，其编号为 $i$。有关编号工作原理的详细信息，请参见样例数据下方的插图。

有时需要同时建立多个连接。为了避免干扰，所有交换机 $S(j)$ ($0 \le j \le n$) 的每个输入和输出最多只能被一个连接使用。给定一组连接请求，您能否为每个请求找到连接路径，使得这些连接路径互不相交？

输入格式

第一行包含一个正整数：测试用例的数量，最多为 100。之后每个测试用例包含：

• 一行，包含两个整数 $n$ ($1 \le n \le 16$) 和 $m$ ($1 \le m \le 2^n$)：最外层交换机的层数和连接请求的数量。
• $m$ 行，每行包含两个整数 $a_i$ 和 $b_i$ ($0 \le a_i, b_i < 2^n$)。每行代表一个从 $S(n)$ 的输入端 $a_i$ 到输出端 $b_i$ 的连接请求。你可以假设整数 $a_i$ 两两不同，且整数 $b_i$ 也两两不同。

输出格式

对于每个测试用例：

• 一行，包含 $m$ 个整数 $s_1, \dots, s_m$，其中 $s_i$ 是建立输入 $a_i$ 到输出 $b_i$ 连接的 $S(0)$ 交换机的编号。

连接路径应当互不相交。你可以输出任何合法的解，并且可以假设至少存在一个合法解。

样例

输入样例 1

2
1 1
0 1
3 5
0 3
1 4
2 5
3 6
4 7

输出样例 1

0
3 0 1 2 4

第二个样例的可能连接方案，加粗的为使用的电缆。