ZING02 - Cheesy line


"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 ≤ 1018

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.



Added by:zing
Date:2018-09-26
Time limit:0.5s-1.799s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All