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

The only programming contests Web 2.0 platform

Server time: Nov/23/2017 23:33:44 (c2).

Desktop version, switch to mobile version.

User lists

Name |
---|