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 |