Problem Statement

On the line of "Yuki Railway", which connects the east and west of the Country of YukiCoder, $2^N + 1$ stations are lined up in a straight line from west to east, and the stations are numbered $0, 1, 2, \dots 2^N$ from the west.

Yuki Railway operates $N + 1$ types of trains, which are named Train $0$, Train $1$, $\dots$, Train $N$.

For $i$ such that $ 0 \leq i \leq N $, Train $i$ stops only at stations whose numbers are multiples of $2^i$.

All trains run from west to east, starting at station $0$ and terminating at station $2^N$. There are no trains running from east to west.

Passengers of Yuki Railway can board any type of train that stops at their current station. They can also get off the train they are on when it stops. They may board and get off any number of times.

Today, $Q$ passengers will use Yuki Railway. For $i$ such that $ 1 \leq i \leq Q $, the $i$-th passenger wants to travel from station $S_i$ to station $T_i$.

For each passenger, solve the following problem.

Problem: When transferring optimally from the departure station $S_i$ to the destination station $T_i$, find the minimum possible number of stations stopped at during the trip, including the destination.

Constraints

• All inputs are integers.
• $ 1 \leq N \leq 60 $
• $ 1 \leq Q \leq 10^5$
• $ 0 \leq S_i < T_i \leq 2^N $

Input

$N$ $Q$
$S_1$ $T_1$
$S_2$ $T_2$
$\vdots$
$S_Q$ $T_Q$

The $1$st line contains $N, Q$ separated by a space.

The following $Q$ lines, starting from line $2$, contain $S_i, T_i$ separated by a space.

Output

Output $Q$ lines. The $i$-th line should contain the answer to the problem for the $i$-th passenger. Print a newline at the end.

Sample

3 4
1 7
3 6
2 3
5 8

4
2
1
2

1 2
0 2
1 2

1
1

32 5
510479020 902533247
494473032 2564665701
1753815 4290493471
3925045722 4058246871
1578437576 3200987099

29
30
43
29
36