F. AB
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given $$$l$$$ and $$$r$$$ and you are asked to calculate the number pairs $$$(a, b)$$$ in that interval interval such that $$$a \lt b$$$, $$$a \oplus b \gt b$$$ and $$$l \le a, b \le r$$$.

Here $$$\oplus$$$ denotes XOR bitwise operation.

If you are unfamiliar with XOR, please visit Esomer's XOR ultimate guide.

Input

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

The first line of each test case contains two integers $$$l$$$, $$$r$$$, $$$(1 \le l \le r \le 10^9)$$$.

Output

You should print the number of pairs that fulfil those conditions.

Example
Input
4
4 8
1 2
8 15
2 6
Output
4
1
0
4