panda is in love with the intervals. but he likes intervals which lie completely inside the given interval [L,R]. now, panda wants to know the number of intervals which are inside the interval[L,R] and the magic value of the interval is greater than zero. help him!
magic value of the interval is the bit wise AND of the numbers which are inside the interval. for example, if interval is [1,4] than it's magic value will be 1 & 2 & 3 & 4 = 0.
Input:
first line will contain the number of test case, and next t lines will contain two integers L and R.
output
output t lines, where ith line is answer for the ith interval.
NOTE: output the remainder after dividing the answer by 10^9+7
constraints
1 <= t <= 10^5
1 <= L <= R <= 10^9
Setter: Mohib Manva
let's consider all interval which lie inside the interval [1,3]:
[1,1], magic value will be 1.
[1,2], magic value will be 1 & 2 = 0.
[1,3], magic value will be 1 & 2 & 3 = 0.
[2,2], magic value will be 2.
[2,3], magic value will be 2 & 3 = 2.
[3,3], magic value will be 3.
so, there are total 4 intervals with magic value greater than 0.
