P13447 [GCJ 2009 #3] Interesting Ranges

A positive integer is a palindrome if its decimal representation (without leading zeros) is a palindromic string (a string that reads the same forwards and backwards). For example, the numbers $5$, $77$, $363$, $4884$, $11111$, $12121$ and $349943$ are palindromes. A range of integers is interesting if it contains an even number of palindromes. The range $[L, R]$, with $L \leqslant R$, is defined as the sequence of integers from $L$ to $R$ (inclusive): $(L, L+1, L+2, \ldots, R-1, R)$. $L$ and $R$ are the range's first and last numbers. The range $[L_1, R_1]$ is a subrange of $[L, R]$ if $L \leqslant L_1 \leqslant R_1 \leqslant R$. Your job is to determine how many interesting subranges of $[L, R]$ there are.

The first line of input gives the number of test cases, $T$. $T$ test cases follow. Each test case is a single line containing two positive integers, $L$ and $R$ (in that order), separated by a space.

For each test case, output one line. That line should contain "Case #x: y", where $x$ is the case number starting with $1$, and $y$ is the number of interesting subranges of $[L, R]$, modulo $1000000007$.

**Limits** - $1 \leqslant T \leqslant 120$ **Small dataset(9 Pts)** - $1 \leqslant L \leqslant R \leqslant 10^{13}$ **Large dataset(23 Pts)** - $1 \leqslant L \leqslant R \leqslant 10^{100}$