Chef and Amazingness of Numbers

All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
Chef defined amazingness of a number n as follows. Let array a denote the decimal representation of n. amazingness of n is defined by following pseudo code.
amazingness(a)
{
set s;
int ans = 0;
for ( int i = 0; i < a.length(); i++ ) {
int val = 0;
for ( int j = i; j < a.length(); j++ ) {
val ^= a[j];
// a[j] denotes digit at jth (0based indexing) position of n counting
from most signficant digit (left to right).
if (val not present in set s before) {
ans += val;
add val to set s
}
}
}
return ans;
}
Given two integers L, R. Find out the following sum : amazingness_{L} + amazingness_{L + 1} + ... + amazingness_{R}. As the answer could be large, print your answer modulo 10^{9} + 7 (1000000007)
Input
 First line of the input contains an integer T denoting the number of test cases.
 Each of the next T lines will contain two space separated integer L, R.
Output
For each test case, output a single integer in separate line corresponding to the value of desired sum.
Constraints
 1 ≤ T ≤ 10
 1 ≤ L, R ≤ 10^{9}.
Subtasks
Subtask #1 : (30 points)
 1 ≤ L, R ≤ 10^{6}
Subtask #2 : (70 points)
 1 ≤ L, R ≤ 10^{9}
Example
Input: 2 1 5 11 14 Output: 15 23
Explanation
Example case 2: The amazingness values of numbers 11, 12, 13, 14 are 1, 6, 6 and 10 respectively. They sum up to 23.
Author:  prateekg603 
Tester:  kevinsogo 
Editorial  http://discuss.codechef.com/problems/CHEFNUM 
Tags  dynamicprogramming, enumeration, may16, prateekg603 
Date Added:  29032016 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, PYP3, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 