← 返回题目列表

Codeforces · 484/A

A. 位

中文机器翻译题面 查看原题

让我们将非负整数 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