D. Equalization
time limit per test
3.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given two non-negative integers $$$x$$$ and $$$y$$$.

You can perform the following operation any number of times (possibly zero): choose a positive integer $$$k$$$ and divide either $$$x$$$ or $$$y$$$ by $$$2^k$$$ rounding down. The cost of this operation is $$$2^k$$$. However, there is an additional constraint: you cannot select the same value of $$$k$$$ more than once.

Your task is to calculate the minimum possible cost in order to make $$$x$$$ equal to $$$y$$$.

Input

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

The only line of each test case contains two integers $$$x$$$ and $$$y$$$ ($$$0 \le x, y \le 10^{17}$$$).

Output

For each test case, print a single integer — the minimum possible cost in order to make $$$x$$$ equal to $$$y$$$.

Example
Input
5
0 1
6 2
3 3
13 37
4238659325782394 12983091057341925
Output
2
6
0
26
32764
Note

In the first example, you can proceed as follows: choose $$$k=1$$$ and divide $$$y$$$ by $$$2$$$. After that, $$$x$$$ and $$$y$$$ are equal to $$$0$$$.

In the second example, you can proceed as follows: choose $$$k=2$$$ and divide $$$x$$$ by $$$4$$$; choose $$$k=1$$$ and divide $$$y$$$ by $$$2$$$. After that, $$$x$$$ and $$$y$$$ are equal to $$$1$$$.

In the third example, numbers already are equal.