這個世界裡的居民都生活在一個有無窮多個房子的城市裡，每個人生活的地方都有唯一的一個編號 $n$ 是一個正整數，這個城市的街道之間可以被這麼構造：對於一個房子 $n$，這個房子連到編號大於它自己的房子的街道只有一條，是連向 $n + \mathrm{lowbit}(n)$ 的。

$\mathrm{lowbit}(n)$ 函數的定義是：$n$ 的二進位分解中只保留最低的有值位。有一種非常方便的位運算方法來計算出來，即 lowbit(n) = n & -n。

可以證明，任意兩個房子都是可以透過這些雙向道路互相到達的，你的任務是處理若干組詢問，計算出兩個房子之間的最短路徑，每經過一條邊則記一單位長度。

輸入格式

第一行一個整數 $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}$