"Why me?", zing asked.

"If you're a star then I'm the darkness. You complete me ",he replied.

Being impressed by him, she gave him an another task.

Build a tree with following rules:

• If a node with (l,r) is given
• Break it into left node with (l,mid)
• Break it into right node with (mid+1,r)
• stop when leaf node appears (l=r)

where mid=(l+r)/2.

So count the number of leaf nodes which do not appear in pairs.

For more clarification, see examples below.

Input

Line 1: No. of queries (<=100000)

Line 2: In next q lines , l r is given (0<=l<=r<=10^18) 

Output

For every query, print the answer.

Example

Input:
2
2 4
4 5
Output:
1
0

Explanation : In (2,4) --> (2,3) and (4,4)
                 (2,3) --> (2,2) and (3,3)
              Here (4,4) is the only leaf node which didn't appear in pair.