让我们将非负整数 x 的二进制表示中的位数(“1”位)表示为 $$\operatorname{popcount}(x)$$。
给您多个由整数对 l 和 r 组成的查询。对于每个查询,找到 x,使得 l ≤ x ≤ r,并且 $$\operatorname{popcount}(x)$$ 是可能的最大值。如果有多个这样的数字,找出其中最小的一个。
输入
第一行包含整数 n — 查询数量 (1 ≤ n ≤ 10000)。
以下 n 行中的每一行都包含两个整数 li、ri — 相应查询的参数 (0 ≤ li ≤ ri ≤ 1018)。
输出
对于每个查询,在单独的行中打印答案。
示例
输入 #1
3 1 2 2 4 1 10
输出 #1
1 3 7
注意
下面列出了从 1 到 10 的数字的二进制表示形式:
110 = 12
210 = 102
310 = 112
410 = 1002
510 = 1012
610 = 1102
710 = 1112
810 = 10002
910 = 10012
1010 = 10102