Or Sum#12338
Sign in

Or Sum

1 second
256 megabytes
Easy

Given integers and , select distinct integers from the range i.e. \{1,2,3,...,n\} such that their bitwise OR is maximized. B : ATTENTION !! : This is very important , you must solve this problem via recursive dfs over bits , otherwise you'll disappoint the writer of the round and you'll end up in a touch-grass situation.

Formally , among all tuples of \{1,2,3,...,n\} , choose any tuple such that a_1 | a_2 | a_3 | .. | a_k is maximized among all tuples and report its value.

Input

The first line contains single integer (1 \le t \le 10^4) — the number of test cases

The only line of each test case contains two integer (1 \le k \le n \le 10^{18}) — the length of required range and the length of tuple.

Output

Output lines, the i_\text{th} line contains the answer to the i_\text{th} test case.

Examples

Example 1

Loading
Loading

Note

For the first test case, we can choose and 1 \mid 2 \mid 4 = 7.

For the second test case, we can choose .

Scoring

  1. Subtask ( points): (\sum n \le 20)

  2. Subtask ( points): No additional constraints