H. Large and even
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Let f(x) be the greatest even divisor of x or 0, if there is no such divisor.

You are given n queries li, ri. For each of them you have to find .

Input

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

Each line of n subsequent lines contains two space-separated integers li and ri (1 ≤ li ≤ ri ≤ 105) — the description of i-th request.

Output

Print n integers. On i-th line print one integer — the answer for the i-th query.

Examples
Input
1
2 12
Output
42
Input
2
1 42
42 45
Output
462
86