You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

稳扎稳打

时间限制：$1s$

空间限制：$256MB$

题目背景

对于一个整数 x , 可以通过一次操作使之变成 x + 1, 或者 2x. 请问最少需要多少次这样的操作可以使得 l 变成 r.

这是一个十分经典的问题, 广度优先搜索可以很好的解决这个问题. 但是今天, lhy 想要来点不一样的.

题目描述

对于一个整数 x, 通过一次操作, 它可以变成[x / 2, x - 1, x + 1, x * 2]中的任意一个. 其中 x / 2 仅当 x 为偶数时可以使用.

例如, 在一次操作后, 3 可以变成[2, 4, 6], 而 4 可以变成[2, 3, 5, 8].

现在 lhy 想要知道, 对于一个闭区间[l, r], 他最少可以在多少次操作后遍历整个区间中的每一个整数. 注意, lhy 可以从这个闭区间的任何一个点出发, 而且他选择的初始点视为已经被遍历.

本题有多组测试.

数据格式

输入

第一行一个正整数 T, 表示测试用例的组数.

每组测试用例一行, 两个整数l, r, 表示需要遍历的区间.

输出

每组测试用例一行, 表示需要的最少操作数.

样例

输入

3
1 1
1 2
3 8

输出

0
1
5

样例解释

前两组显然. 对于第三组, 从 3 开始, 遍历顺序为 [3, 6, 5, 4, 8, 7]

数据范围及约定

$-10^9 \le l,r \le 10^9$

$T\le 10^5$.