Interesting Ranges

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.

For integers $L \le R$, the range $[L, R]$ is the sequence of integers from $L$ to $R$ inclusive: $(L, L+1, L+2, \dots, R-1, R)$. A range is interesting if the number of palindromes in it is even. A range with no palindrome at all is interesting, because zero is even.

The range $[L_1, R_1]$ is a subrange of $[L, R]$ if $L \le L_1 \le R_1 \le R$. Given $L$ and $R$, count the interesting subranges of $[L, R]$.

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

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.

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