海龟和小猪正在玩数字游戏。
首先,Turtle 将选择一个整数 $$$x$$$,使得 $$$l \le x \le r$$$,其中给出 $$$l, r$$$。它还保证 $$$2l \le r$$$。
然后,Piggy会继续执行以下操作,直到$$$x$$$变成$$$1$$$:
- 选择一个整数 $$$p$$$,使得 $$$p \ge 2$$$ 和 $$$p \mid x$$$ (即 $$$x$$$ 是 $$$p$$$ 的倍数)。
- 将$$$x$$$设置为$$$\frac{x}{p}$$$,分数将增加$$$1$$$。
分数最初为 $$$0$$$。海龟和小猪都希望得分最大化。请帮助他们计算最高分。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。
每个测试用例的第一行包含两个整数 $$$l, r$$$ ($$$1 \le l \le r \le 10^9, 2l \le r$$$) — Turtle 可以从中选择整数的范围。
输出
对于每个测试用例,输出一个整数 - 最高分数。
示例
输入 #1
5 2 4 3 6 2 15 6 22 114514 1919810
输出 #1
2 2 3 4 20
注意
在第一个测试用例中,Turtle 可以选择一个整数 $$$x$$$,使得 $$$2 \le x \le 4$$$。他可以选择$$$x = 4$$$。那么小猪可以选择 $$$p = 2$$$ 进行 $$$2$$$ 次。之后,$$$x$$$ 将变为 $$$1$$$,分数将为 $$$2$$$,即最大化。
在第二个测试用例中,Turtle 可以选择一个整数 $$$3 \le x \le 6$$$。他可以选择$$$x = 6$$$。那么小猪可以选择$$$p = 2$$$,然后选择$$$p = 3$$$。之后,$$$x$$$将变为$$$1$$$,分数将为$$$2$$$,即最高分。
在第三个测试用例中,Turtle 可以选择 $$$x = 12$$$。
在第四个测试用例中,Turtle 可以选择 $$$x = 16$$$。