题目描述

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$.

3
1 2
1 7
12 110

Case #1: 1
Case #2: 12
Case #3: 2466

提示

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}$