A telephone company wants to build a new telephone network in a city. The company has the goal that each person in the city should be able to call each other person. Of course, it is not possible to build direct connections between every pair of persons. Instead, the company uses a network made up of several layers. We denote a network switch in layer \textbf{j} by \textbf{S(j)}. A switch \textbf{S(0)} consists of one input, one output and a cable connecting the input to the output. A switch \textbf{S(j)} with \textbf{j} > \textbf{0} consists of \textbf{2^j} inputs, \textbf{2^j} outputs and two switches \textbf{S(j-1)}. Input \textbf{i} of \textbf{S(j)} (\textbf{0} ≤ \textbf{i} ≤ \textbf{2^j} ) is connected via a cable to the inputs \textbf{i mod 2^\{j-1\}} of each of the two switches \textbf{S(j-1)}. Similarly, output \textbf{i} of \textbf{S(j)} is connected to the outputs \textbf{i mod 2^\{j-1\}} of each of the two switches \textbf{S(j-1)}. \includegraphics{https://static.e-olymp.com/content/46/4642082185ccfa08590f66cc3ce0bc3b8626322e.jpg} The connections between a switch \textbf{S(j)} and the two switches \textbf{S(j-1)} it consists of. We are considering a network with one switch \textbf{S(n)} in the outermost layer. It can be shown that any input and output of switch \textbf{S(n)} has a unique connection path to any of the \textbf{S(0)} switches. Therefore, any input of \textbf{S(n)} can be connected to any of its outputs, and the connection path is uniquely determined by specifying through which switch \textbf{S(0)} the connection is established. We number the switches \textbf{S(0)} belonging to the switch \textbf{S(n)} from \textbf{0} to \textbf{2^\{n-1\}}. The \textbf{i}-th switch \textbf{S(0)} is defined as follows. Write the number \textbf{i} in binary as \textbf{b_\{n-1\}} \textbf{b_\{n-2\}} ... \textbf{b_0}. This defines a path from an input of \textbf{S(n)} to the \textbf{i}-th switch \textbf{S(0)} via the following procedure: for each \textbf{j}, \textbf{b_j = 0} indicates that the path extends from \textbf{S(j+1)} to the first \textbf{S(j)} switch to which it is directly connected, and \textbf{b_j = 1} indicates that the path extends to the second \textbf{S(j)} switch. Note that regardless of which input of \textbf{S(n)} is selected, this path arrives at the same \textbf{S(0)} switch, which is given the number \textbf{i}. See also the figure below the sample data for details of how the numbering works. Sometimes multiple connections are needed at the same time. In order to avoid interference, each of the inputs and outputs of all switches \textbf{S(j)} (\textbf{0} ≤ \textbf{j} ≤ \textbf{n}) can be used by at most one connection. Given a set of connection requests, can you find connection paths for each request such that the connection paths are disjoint? \InputFile On the first line a positive integer: the number of test cases, at most \textbf{100}. After that per test case: \begin{itemize} \item One line with two integers \textbf{n} (\textbf{1} ≤ \textbf{n} ≤ \textbf{16}) and \textbf{m} (\textbf{1} ≤ \textbf{m} ≤ \textbf{2^n}): the layer of the outermost switch and the number of connection requests. \item \textbf{m} lines, each with two integers \textbf{a_i} and \textbf{b_i} (\textbf{0} ≤ \textbf{a_i}, \textbf{b_i} < \textbf{2^n}). Each such line represents a connection request from input number \textbf{a_i} of \textbf{S(n)} to output number \textbf{b_i}. You may assume that the integers \textbf{a_i} are pairwise distinct, and the integers \textbf{b_i} are pairwise distinct as well. \end{itemize} \OutputFile Per test case: \begin{itemize} \item One line with m integers \textbf{s_1}, ..., \textbf{s_m}, where \textbf{s_i} is the number of the \textbf{S(0)} switch through which the connection of input \textbf{a_i} to output \textbf{b_i} is established. \end{itemize} The connection paths should be disjoint. You may print any valid solution, and you may assume that there is at least one valid solution. \textbf{Hint} \includegraphics{https://static.e-olymp.com/content/34/344d3bede18272da13e86d8f02e16c5cf3dade59.jpg} A possible connection scheme for the second sample case, with used cables in bold. \textbf{Note:} Special judge problem, you may get "Wrong Answer" when output in wrong format.