# 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!

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

#### Samples

Input | Output |
---|---|

3 3 4 1 6 22 121 | Case 1: 2 Case 2: 12 Case 3: 2530 |

Login to submit