"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: Number of queries (≤ 100000)

Line 2: In next q lines, l r is given (0 ≤ l ≤ r ≤ 10¹⁸) 

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.