問題文

YukiCoder国を東西に結ぶ「Yuki鉄道」の路線には、西から東へ一直線状に $2^N + 1$ 個の駅が並んでおり、駅には西から $0, 1, 2, \dots 2^N$ と番号がついています。

また、Yuki鉄道では $N + 1$ 種類の列車が運行しており、列車には $0$ 号列車、 $1$ 号列車、 $\dots$ $N$ 号列車と名前がついています。

$ 0 \leq i \leq N $ である $i$ について、 $i$ 号列車は番号が $2^i$ の倍数である駅にのみ停車します。

すべての列車は西から東へ運行し、始点が駅 $0$ で、終点が駅 $2^N$ です。東から西へ向かう列車はありません。

Yuki鉄道の利用客は、現在いる駅に停車する種類の列車に乗ることができます。また、乗っている列車が停車した時、降りることができます。乗り降りは何度でも可能です。

さて、今日は $Q$ 人の利用客がYuki鉄道を利用します。$ 1 \leq i \leq Q $ である $i$ について、$i$ 番目の利用客は駅 $S_i$ から $T_i$ へ移動しようと考えています。

それぞれの利用客について、以下の問題を解いてください。

問題:出発地の駅 $S_i$ から到着地の駅 $T_i$ への乗り継ぎを最適に行った場合、到着地を含めて移動過程で停車する駅の数として考えられる最小値を求めてください。

制約

• 入力は全て整数
• $ 1 \leq N \leq 60 $
• $ 1 \leq Q \leq 10^5$
• $ 0 \leq S_i < T_i \leq 2^N $

入力

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

$1$ 行目に $N, Q$ が空白区切りで与えられる。

$2$ 行目から、 $Q$ 行にわたって $S_i, T_i$ が空白区切りで与えられる。

出力

$Q$ 行にわたって出力せよ。　$i$ 行目には、 $i$ 番目の利用客についての問題の答えを出力せよ。 最後に改行すること。

サンプル

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