Bajtopa is one of the continents on the planet Bajtocja. It contains many countries, which for simplicity have been numbered with consecutive non-negative integers from $A$ to $B$ inclusive. Each number in this range corresponds to exactly one country, while other numbers (those smaller than $A$ and those larger than $B$) correspond to countries located on other continents. The authorities of the countries of Bajtopa understand that their further development requires integration. Therefore, they have formed an economic and political alliance called the Bajtopejska Union.

Until now, the only way to travel between the countries of Bajtopa was by road. The time has come to change this once and for all: the Bengen zone project involves creating a network of air connections that guarantees the possibility of communication (not necessarily direct) between any two countries in the Union.

Naturally, it was decided that the network should be as cheap as possible. The cost of creating an air connection between countries numbered $x$ and $y$ is $x \oplus y$ bajtalars, where $\oplus$ denotes the exclusive OR (XOR) operation: the $i$-th bit of the result of $x \oplus y$ is equal to 1 if and only if exactly one of the $i$-th bits of the numbers $x$ and $y$ is equal to 1.

The Union authorities would like to know the cost of building the network before they start negotiating the details of the Bengen zone project. Help them and write a program that determines this cost.

Input

The first line of the input contains a single natural number $q$ ($1 \le q \le 100\,000$), representing the number of data sets. The following $q$ lines contain descriptions of the data sets, one per line. The description of each data set consists of two non-negative integers $A$ and $B$ ($0 \le A \le B \le 10^{16}$).

Output

Your program should output exactly $q$ lines. The $i$-th line should contain the answer for the $i$-th data set. The answer for each data set is a single integer – the minimum possible cost of creating the Bengen zone.

Examples

Input 1

1
2 5

Output 1

8

Note

The countries of Bajtopa have numbers $\{2, 3, 4, 5\}$. It is sufficient to create only three air connections: between countries 2 and 3 (cost: $2 \oplus 3 = 1$), 2 and 4 (cost: $2 \oplus 4 = 6$), and 4 and 5 (cost: $4 \oplus 5 = 1$). The total cost of creating the network is therefore $1 + 6 + 1 = 8$ bajtalars.

Evaluation

The test suite is divided into the following subtasks. Tests for each subtask consist of one or more separate test groups.

Sample Tests

1ocen: $q = 1, A = 0, B = 17$ 2ocen: $q = 1, A = 50\,000, B = 200\,000$ 3ocen: $q = 1, A = 0, B = 2^{40}$ 4ocen: $q = 40$, in the $i$-th query $A = 2^{i-1} + 1, B = 2^i$