Surely anyone studying computer science is familiar with the following puzzle when learning about recursion.

Given a board of size ~2^k \times 2^k~ and L-shaped tiles made up of 3 squares. The tiles can be rotated freely. Find a way to place the tiles on the board so that, except for the cell ~(r, c)~, all cells on the board are covered by exactly one tile.

The key to solving this puzzle is to realize that we can create larger L-shaped tiles from smaller ones and use the larger tiles to cover the board. To help you remember, a summary of the general algorithm to solve this puzzle will be described in the notes section below.

After teaching you this algorithm, the teacher was amazed to see that you understood and could apply it very quickly. The teacher then had to assign additional exercises related to this algorithm. Given a board of size ~2^k \times 2^k~, the rows are numbered ~0, 1, 2, \ldots, 2^k - 1~ from top to bottom, and the columns are numbered ~0, 1, 2, \ldots, 2^k - 1~ from left to right. Initially, the board has been covered with L-shaped tiles such that the cell ~(0, 0)~ is the uncovered cell according to the algorithm you have learned.

Then the teacher has ~q~ consecutive small puzzles. For the ~i~-th puzzle, the teacher wants to change the board from the state just before this puzzle to the state where the cell ~(r_i, c_i)~ is uncovered. To do this, the teacher allows you to perform the following operation (zero or more times):

• Choose an L-shaped tile that is adjacent to 2 edges of the uncovered cell. Rotate this tile 90 degrees in the direction you want. It can be seen that after this operation, a new cell will become the uncovered cell.

It can be shown that, with the initial tiling according to the algorithm you have learned, there is always a sequence of operations to rotate the tiles to change the uncovered cell from one cell to another.

Below is an illustration of how to perform the operation for the ~2^2 \times 2^2~ board. The teacher has posed three puzzles, each requiring the uncovered cell to be transformed as follows:

• From cell ~(0, 0)~ to cell ~(2, 1)~, with 3 operations.

• From cell ~(2, 1)~ to cell ~(0, 3)~, with 4 operations.

• From cell ~(0, 3)~ to cell ~(0, 0)~, with 5 operations.

The teacher wants you to solve the puzzles as quickly as possible. Therefore, for each puzzle, you want to find out the minimum number of operations needed to answer that puzzle.

Input

The first line contains two integers ~k~ and ~q~ (~1 \le k \le 60~, ~1 \le q \le 10^5~). The parameter ~k~ indicates that the size of the board is ~2^k \times 2^k~, and the teacher will ask you ~q~ puzzles.

The ~i~-th line in the following ~q~ lines contains two integers ~r_i~ and ~c_i~ (~0 \le r_i, c_i < 2^k~)  – the uncovered cell after the ~i~-th puzzle.

Output

Print ~q~ lines. The ~i~-th line contains an integer representing the minimum number of operations to solve the ~i~-th puzzle.

Scoring

Sample Input 1

2 3
2 1
0 3
0 0

Sample Output 1

3
4
5

Sample Input 2

3 4
6 2
7 7
3 4
4 6

Sample Output 2

10
10
7
5

Notes

The first example has been illustrated in the image above.

Below is an illustration for the second example.

Summary of the L-shaped tile covering algorithm

From small L-shaped tiles, we can create larger L-shaped tiles by combining them as follows:

To cover the board with L-shaped tiles, ensuring that the cell ~(0, 0)~ is not covered, we can combine them into larger L-shaped tiles and stack them as follows: