2017 计算机系暑期夏令营机考

B. 1 的个数最多的整数

单点时限: 2.0 sec

内存限制: 256 MB

给定整数 $a$ 和 $b$,输出区间 $[a, b]$ 中对应二进制表示含 1 的个数最多的整数。

如果存在多个解,则输出符合条件的最小的整数。

输入格式

第一行一个整数 $T$ $(1 \leq T \leq 10^4)$,表示问题数。

接下来 $T$ 行,每行两个整数 $a, b$ $(0 \leq a \leq b \leq 2^{63}-1)$。数据之间用一个空格分隔。

共有两组数据,分别为小数据和大数据,大数据范围如上。对于小数据:$T \leq 10, a \leq b \leq 5 \cdot 10^6$。

输出格式

对于每个问题,输出一行 Case x: y,其中 x 是问题编号,从 1 开始,y 是答案。

样例

Input
3
0 14
100 1000
3966869755091699093 4597827455649079876
Output
Case 1: 7
Case 2: 511
Case 3: 4035225266123964415

提示

第一个样例数据:$a=0,b=14$,在 $[0,14]$ 之间含 1 最多的整数为 $7(0111),11(1011),13(1101),14(1110)$,输出最小的整数为 $7$。

注意,第三组样例不会出现在小数据中。