この世界の住人は、無限に家が並ぶ都市に住んでいます。各住居には $n$ という正整数の番号が一つずつ割り当てられています。この都市の道路は次のように構成されています。ある家 $n$ から、自分より番号が大きい家へ向かう道路はただ一つ存在し、それは $n + \mathrm{lowbit}(n)$ へと繋がっています。

$\mathrm{lowbit}(n)$ 関数は、$n$ を二進数で表したときに最も低い位にある $1$ のみを残した値として定義されます。これはビット演算を用いて lowbit(n) = n & -n と計算することができます。

任意の二つの家は、これらの道路（双方向）を通って互いに行き来できることが証明できます。あなたのタスクは、与えられた複数のクエリに対して、二つの家を結ぶ最短経路の長さを求めることです。道路を一つ通るごとに長さは $1$ とします。

入力

一行目にクエリの数 $q$ が与えられます。

続く $q$ 行の各行には、二つの正整数 $x, y$ が与えられ、これら二つの家を結ぶ最短経路を求めるクエリを表します。

出力

$q$ 行にわたって、各クエリに対する最短経路の長さを出力してください。

入出力例

入出力例 1

2
1 3
2 4

出力例 1

3
1

小課題

• $20\%$ のデータについて、$1 \leq q \leq 10$, $1 \le x,y \le 2^{3}$ を満たす。
• $30\%$ のデータについて、$1 \leq q \leq 500$, $1 \le x,y \le 2^{9}$ を満たす。
• $70\%$ のデータについて、$1 \leq q \leq 10^5$, $1 \le x,y \le 2^{20}$ を満たす。
• $100\%$ のデータについて、$1 \leq q \leq 3 \times 10^5$, $1 \le x, y \le 2^{60}$ を満たす。