“Is that a British Army Browning L9A1 in your pocket, or are you just pleased to see me?” -Moriarty

Problem 5

You are given 2 positive integers l and r. Now you need to find out number of integers in range l to r which contains even number of set bits in its binary representation.

Input :

First line of the input consists of number of test cases T.

Next T lines contains 2 positive integers l and r.

Output:

A single integer representing count of numbers in range l to r which contains even number of 1s. As the answer can be large take modulo with $10^9+7$ .

Constraints:

$1 \le T \le 10^5$

$1 \le l \le r \le 10^{18}$