A long binary string is formed via the following process:

1. Start with the string 1.
2. Every second, we replace each 1 of the current string with 10 and each 0 of the current string with 1.

The state of the string in the first few seconds is as follows: $1, 10, 101, 10110, 10110101$.

Let $s$ be the string obtained at the end of the process after running it for $10^{100}$ seconds. You want to answer $Q$ queries of the following type: how many ones are there between the $l$-th character and $r$-th character (inclusive) of $s$?

Input

The first line contains a single integer $Q$ ($1 \le Q \le 300\,000$), denoting the number of queries.

The next $Q$ lines each contain two space-separated integers $l,r$ ($1 \le l \le r \le 10^{18}$), representing the queries.

Output

For each query, output the number of ones between the $l$-th character and $r$-th character (inclusive) of $s$.

Example

Input

3
3 9
6 6
1 12

Output

5
1
8

Explanation

One can show that the first $12$ characters of the string are $101101011011$.

For the first query, there are $5$ ones between the 3rd character and 9th character. The relevant substring is $1101011$.

For the second query, there is $1$ one between the 6th character and 6th character. The relevant substring is $1$.

For the third query, there are $8$ ones between the 1st character and 12th character. The relevant substring is $101101011011$.

Scoring

Subtask $1$ ($7$ points): $Q = 1$, $r \le 300\,000$

Subtask $2$ ($10$ points): $l = 1$, $r \le 300\,000$

Subtask $3$ ($13$ points): $r \le 300\,000$

Subtask $4$ ($20$ points): $l=1$, $r$ is equal to the length of the string after some integer number of seconds.

Subtask $5$ ($15$ points): $l=r$

Subtask $6$ ($15$ points): $Q = 1$

Subtask $7$ ($10$ points): $r \le 10^9$

Subtask $8$ ($10$ points): No additional constraints