Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ACM-ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

A. Bits

time limit per test

1 secondmemory limit per test

256 megabytesinput

standard inputoutput

standard outputLet's denote as the number of bits set ('1' bits) in the binary representation of the non-negative integer *x*.

You are given multiple queries consisting of pairs of integers *l* and *r*. For each query, find the *x*, such that *l* ≤ *x* ≤ *r*, and is maximum possible. If there are multiple such numbers find the smallest of them.

Input

The first line contains integer *n* — the number of queries (1 ≤ *n* ≤ 10000).

Each of the following *n* lines contain two integers *l*_{i}, *r*_{i} — the arguments for the corresponding query (0 ≤ *l*_{i} ≤ *r*_{i} ≤ 10^{18}).

Output

For each query print the answer in a separate line.

Examples

Input

3

1 2

2 4

1 10

Output

1

3

7

Note

The binary representations of numbers from 1 to 10 are listed below:

1_{10} = 1_{2}

2_{10} = 10_{2}

3_{10} = 11_{2}

4_{10} = 100_{2}

5_{10} = 101_{2}

6_{10} = 110_{2}

7_{10} = 111_{2}

8_{10} = 1000_{2}

9_{10} = 1001_{2}

10_{10} = 1010_{2}

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Feb/21/2018 14:38:52 (d2).

Desktop version, switch to mobile version.

User lists

Name |
---|