这个世界里的居民都生活在一个有无穷多个房子的城市里，每个人生活的地方都有唯一的一个编号 $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 \le q \le 3 \times 10^5$, $1 \le x, y \le 2^{60}$