Interesting Ranges (Small)

A positive integer is a palindrome if its decimal representation, written without leading zeros, reads the same forwards and backwards. For example, 5, 77, 363, 4884, 11111, 12121 and 349943 are palindromes.

A range of integers is interesting if it contains an even number of palindromes. For $L \le R$, the range $[L, R]$ is the sequence of integers from $L$ to $R$ inclusive, that is $(L, L+1, L+2, \dots, R-1, R)$, and $L$ and $R$ are its first and last numbers. Zero is even, so a range that contains no palindrome at all is also interesting.

The range $[L_1, R_1]$ is a subrange of $[L, R]$ if $L \le L_1 \le R_1 \le R$. Determine how many subranges of $[L, R]$ are interesting.

The first line contains the number of test cases $T$. Each of the next $T$ lines describes one test case and contains two positive integers $L$ and $R$, in that order, separated by a single space.

Limits

• $1 \le T \le 120$
• $1 \le L \le R \le 10^{13}$

For each test case, print one line in the form Case #x: y, where $x$ is the test case number starting from 1 and $y$ is the number of interesting subranges of $[L, R]$ modulo $1000000007$.