Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems.
×

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-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jul/09/2020 15:18:53 (i1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|