小沙跳悬崖，经典咏流传(easy version)

题号：NC266546
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

本题有对应的hard version，区别仅在数据范围，保证easy version的测试用例集是hard version的真子集，通过困难版本的代码可直接通过简单版本。

小沙学会了影分身之术，他和他的分身们一共 $10^{18}$ 只小沙现在使用钩爪固定在一个随时间逐渐合拢的悬崖两侧，如果小沙能说出悬崖两侧的距离，那么悬崖就会停止合拢，否则悬崖就会把这群小沙挤死。

具体来讲，一开始小沙们知道的信息为：悬崖两侧的距离不小于 $l$ 且不大于 $r$ 。

接下来每个时刻按照顺序依次进行如下操作。

1、询问小沙们是否知道悬崖两侧的距离，若小沙不知道则不能进行回答（小沙不能猜一个答案，你可以认为一旦小沙猜错，悬崖会立刻以光速合拢，压死所有小沙），若小沙们此时知道答案，悬崖立即停止合拢，剩余的小沙全部存活。

2、小沙们选择一只小沙从悬崖的一侧跳向另一侧，且弹跳的距离为 $x$ ，小沙可以自己任意选择 $x$ 的值，若悬崖两侧的距离大于 $x$ ，则这只小沙会摔死，否则这只小沙还活着，还可以进行下一次弹跳。

3、悬崖合拢 $1$ 个单位，若合拢后悬崖两侧的距离为 $0$ ，则立即压死所有的小沙。

小沙必须在某一轮操作中进行“回答”并且正确才可以停止悬崖的合拢，并结束所有过程，而不是当他“知道”悬崖的答案时。

如果小沙的运气非常差，那么在最坏的可能下，小沙们使用最优策略，此时至少死亡多少只小沙？

输入描述:

第一行输入一个正整数表示测试用例的组数。

对于每组测试用例，输入两个非负整数。表示小沙们一开始知道的信息。

输出描述:

对于每个测试用例，输出一个非负整数，表示在最坏的可能下，小沙们使用最优策略时死亡的小沙数目。

示例1

输入

复制

输出

复制

0
1000000000000000000
1
48

说明

对于第一个样例：
小沙在第一轮直接推理出当前悬崖的长度为，所以没有小沙会被压死或者跳崖身亡。

对于第二个样例：
如果小沙选择第一轮令这个长度跳崖，虽然此时小沙不会死，但是也没有得到任何有用的信息。
如果小沙选择第一轮令这个长度跳崖，有两种情况，摔死了或者没摔死，如果没摔死，则说明当前悬崖长度就是。但是由于第一轮在小沙跳崖后，悬崖的尺寸会合拢减少，此时悬崖完全合并，没有下一轮再让小沙回答悬崖的长度了，导致所有的小沙都被压死了。题目要求“最坏情况”，所以答案为。

对于第三个样例：
具体情况同第二个样例，但是此时由于悬崖合拢个单位后也不会压死所有小沙，所以至多摔死一个小沙，然后小沙在下一轮回答悬崖的长度，然后结束。

对于第四个样例：
如果小沙第一轮不选择令这个长度跳崖，那么接下来的最坏情况都将导致所有小沙都被压死。类似的，接下来的任意轮中，小沙都会选择这个长度跳崖。