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 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)
For each test case, print the case number and the number of odd-ranges modulo 1000000007
Input | Output |
---|---|
3 3 4 1 6 22 121 | Case 1: 2 Case 2: 12 Case 3: 2530 |