Captain Jack Sparrow#12293
Jack Sparrow is one of the greatest captains. When he discovered a new treasure, he counted the number of coins. However, when he went to check his coins later, he realized that some of them were missing. Jack Sparrow is a very precise person, so he wants to determine how many coins he has lost.
He noticed that for each segment of his journey, from the -th kilometer to the -th kilometer, the number of coins he loses in each kilometer is calculated as:
Where represents the bitwise AND operation, and represents the bitwise XOR operation.
Jack also knows he traverses from the -th kilometer to the -th kilometer where a \leq l \leq r \leq b for all and in different times.
Now, the captain wants to find the number of lost coins. Formally, compute the following:
The first line contains a single integer (1 \le t \leq 10^4) — the number of test cases.
Each test case contains two integers , (1 \leq a \leq b \leq 10^{9}, b - a \leq 2\cdot10^5) — the boundaries of the range.
It is guaranteed that the \sum (b-a) over all test cases does not exceed 2\cdot10^5.
For each test case, print the number of lost coins modulo 10^9 + 7.
Example 1
In the first test case, Captain didn't move, so he didn't lose any coin.
In the second test case, Captain traverses these ranges:
: He lost (2\ \&\ 3) + (2\ \oplus \ 3) = 3 coins for each kilometer. There is one kilometer, so he lost coins for this range.
: He lost (2\ \&\ 4) + (2\ \oplus \ 4) = 6 coins for each kilometer. There are two kilometers. In the first kilometer, he lost coins, and in the second kilometer, he lost coins. So, he lost coins totally for this range.
: He lost (3\ \&\ 4) + (3\ \oplus \ 4) = 7 coins for each kilometer. There is one kilometer, so he lost coins for this range.
Finally, Captain lost 3 + 12 + 7 = 22 coins.
Subtask ( points) : (1 \le a \le b \le 40)
Subtask ( points) : (1 \le \sum (b-a) \le 1000)
Subtask ( points) : No additional constraints