3080: XOR

Exclusive or is a logical operation that outputs true only when inputs differ(one is true, the other is false). It is symbolized by the infix operators such as $XOR$, $\oplus$.

This time, brave $QQQ$ raises a problem to you. Given an interval [$l, r$], you need to calculate how many numbers $x$ between $l$ and $r$, where $x$ satisfies $x \oplus 4x \oplus 5x = 0$.

The first line contains an integer number $T$ ($1 \leq T \leq 60$), the number of test cases.

$i^{th}$ of each next $T$ lines contains two integers $l$, $r$ ($1 \leq l \leq r \leq 10^{18}$).

For each test case print the answer.

2
2 6
1 109

4
39