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!

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

Samples

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

Discussion