Kaosar and Triples#12263
You will be given two integers and you have to find the number of ordered triplets (a,b,c) where a<b<c and a\oplus b=c, a\oplus c=b, b\oplus c =a and (l \leq a, b, c \leq r).
Since the number may be very large, print it modulo 10^9+7.
The first line will contain a single integer (1 \le t \le 10^4) — the number of test cases.
The only line of each test contains two integers and (1\leq l < r \leq 10^{18}) — the query boundaries.
For each test case, output one line — the number of triples modulo 10^9 + 7.
Example 1
Subtask ( points): \sum r - l + 1 \le 1000
Subtask ( points): \sum r - l + 1 \le 10^6
Subtask ( points): r - l + 1 \le 10^9
Subtask ( points) : No additional constraints.