E. Counting VIP Guests
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

A small kingdom consists of one road. Every house on the street is numbered sequentially from $$$A$$$ to $$$B$$$ $$$(A, A + 1, \dots, B - 1, B)$$$. The key number of a house is the largest odd divisor of the house number.

The king is throwing a party and wants to invite a select number of VIP guests. Only guests living in houses with a key number of $$$1$$$ are allowed to attend the party.

To estimate how much food and how many drinks he needs to buy, the king wants to know how many VIP guests there are.

Input

The first line of the input contains a single integer $$$t$$$ ($$$1 \leq t \leq 2 \cdot 10^5$$$), the number of test cases.

The first line of each test case contains two integers $$$A$$$ $$$(1 \leq A \leq 10^{18})$$$, the first house number, and $$$B$$$ $$$(A \leq B \leq 10^{18})$$$, the last house number.

Output

For each test case, print the number of invited VIP guests; that is, the number of houses where the key number is 1.

Example
Input
3
1 5
30 35
1 1000000
Output
3
1
20