题目描述

给定满足 $L\le R$ 的正整数 $L$ 和 $R$。

对于长度为 $R-L+1$ 的正整数序列 $A=(A_L,A_{L+1},\ldots,A_R)$，若它满足以下条件，则称其为好整数序列：

• 对于所有满足 $L\le i < j\le R$ 的整数对 $(i,j)$，若 $A_i = A_j$，则 $\operatorname{popcount}(i)<\operatorname{popcount}(j)$。

求所有好整数序列 $A=(A_L,A_{L+1},\ldots,A_R)$ 中 $\max(A_L,A_{L+1},\ldots,A_R)$ 的最小值。

共有 $T$ 组测试数据，请对每组分别求解。

什么是 $\operatorname{popcount}$？ 对于非负整数 $x$，$\operatorname{popcount}(x)$ 表示 $x$ 的二进制表示中 $1$ 的个数。更准确地说，若非负整数 $x$ 满足 $\displaystyle x=\sum _ {i=0} ^ \infty b _ i2 ^ i\ (b _ i\in\lbrace0,1\rbrace)$，则 $\displaystyle\operatorname{popcount}(x)=\sum _ {i=0} ^ \infty b _ i$。

例如，$13$ 的二进制表示为 1101，因此 $\operatorname{popcount}(13)=3$。

输入格式

输入按以下格式从标准输入读入：

• $T$
• $\text{case}_1$
• $\text{case}_2$
• $\vdots$
• $\text{case}_T$

每个测试用例按以下格式给出。

• $L$ $R$

输出格式

输出 $T$ 行。

第 $i$ 行 $(1\le i\le T)$ 应输出第 $i$ 个测试用例 $\text{case}_i$ 的答案。

5
3 6
1 1
2 15
100 10000000
514284786278117031 620546740167642909

3
1
6
1636985
11375123021856567

考虑第一个测试用例。

$(A_3,A_4,A_5,A_6)=(1,2,2,3)$ 是一个好整数序列，且 $\max(A_3,A_4,A_5,A_6)=3$。

不存在使 $\max(A_3,A_4,A_5,A_6) < 3$ 的好整数序列，因此第一行输出 $3$。

数据范围

• $1\le T\le 10^4$

• $1\le L \le R\le 10^{18}$

• 所有输入值均为整数。

• 来源：AtCoder ABC 476 G

子任务设置

• 子任务 1（30 分）：$T \le 100$ 且 $R \le 10^6$。
• 子任务 2（30 分）：$T \le 1000$ 且 $R \le 10^{12}$。
• 子任务 3（40 分）：无特殊限制。