Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

That's Odd!

By d1xlord · Limits 4s, 1.0 GB

People always say that you’re odd and you like being the odd person in a room! You’re so odd that you like every odd things in the world. Just like a palindrome, as it’s quite odd. Recently you are infatuated with palindromic numbers. (A palindromic number is a number, in decimal base and without leading zeros, that is the same when written forwards or backwards)

You are very quick in figuring out the palindromic numbers within a range, and if some range has odd number of palindromic-numbers, you call them odd-range. But the task ahead of you is a bit different. Given a range (L, R) where (L ≤ R), you have to figure out how many subranges (l, r) are odd-ranges, where (L ≤ l and r ≤ R).

Input

Input starts with an integer T (≤ 150), denoting the number of test cases. Each test case contains two integers (L, R), where (1 ≤ L, R ≤ 10^12)

Output

For each test case, print the case number and the number of odd-ranges modulo 1000000007

Sample

InputOutput
```3
3 4
1 6
22 121
```
```Case 1: 2
Case 2: 12
Case 3: 2530
```

Statistics

95% Solution Ratio

siam_cr7Earliest, Oct '17

experimenterFastest, 0.4s

Tarik.amtolyLightest, 16 MB

experimenterShortest, 1596B

Related Contests

 IUT 9th ICT Fest 2017 Programming Contest Ended Oct '17 Replay of IUT 9th ICT Fest 2017 Programming Contest Ended Oct '17