B. Binahuatls Prophecy
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

The year 2012 started a trend when everybody tried to predict the end of the world, they always find something peculiar in the number that indicates that it will really be the end of the world.

One famous group was an old Mexican tribe called the Binahuatls, who predicted that the world will be ending in a year where the binary representation it's a palindrome, meaning that the number it's the same if we were to reading forward or backward.

But as you, the person sitting in a chair, reading this problem in a contest or in practice, that is thinking about what the question of this problem is, are a living example that the world hasn't ended yet. The most eager fans of the Binahuatl defend that the world will end in a binary palindromic year for sure.

Given two dates $$$A$$$ and $$$B$$$ help those eager fans to know how many binary palindromic years exists between $$$A$$$ and $$$B$$$ inclusive!

Input

The first line contains a single integer $$$Q$$$ $$$(1 \leq Q \leq 10^5)$$$, representing the number of test cases.

Each of the following $$$Q$$$ lines contains two integer numbers separated by a space $$$A$$$ and $$$B$$$ $$$(0 \leq A \leq B \lt 2^{31})$$$.

Output

Print $$$Q$$$ lines, where the $$$i$$$-th line contains a single integer number representing the answer for the $$$i$$$-th test case from the input.

Examples
Input
1
1 10
Output
5
Input
3
10 10
4 4
2 2
Output
0
0
0
Input
4
123 1234
2000 2022
10 100
100 1000
Output
47
1
14
42