"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 did'nt appear in pair.