Description

如果一个正整数的十进制表示（不含前导零）是回文字符串（即正着读和反着读都一样），那么这个数就是回文数。例如，$5$、$77$、$363$、$4884$、$11111$、$12121$ 和 $349943$ 都是回文数。

如果一个区间内包含偶数个回文数，则称该区间是有趣的。区间 $[L, R]$，其中 $L \leqslant R$，定义为从 $L$ 到 $R$ 的所有整数组成的序列：$(L, L+1, L+2, \ldots, R-1, R)$。$L$ 和 $R$ 分别是区间的起点和终点。

如果 $L \leqslant L_1 \leqslant R_1 \leqslant R$，则区间 $[L_1, R_1]$ 是 $[L, R]$ 的一个子区间。你的任务是统计 $[L, R]$ 的所有有趣子区间的个数。

Input Format

输入的第一行为测试用例数 $T$。接下来有 $T$ 组测试数据。每组测试数据为一行，包含两个正整数 $L$ 和 $R$（按顺序），用空格分隔。

Output Format

对于每组测试数据，输出一行，格式如下：

Case #$x$: $y$

其中 $x$ 表示测试编号（从 $1$ 开始），$y$ 表示 $[L, R]$ 中有趣子区间的个数，对 $1000000007$ 取模。

3
1 2
1 7
12 110

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

Hint

限制条件

• $1 \leqslant T \leqslant 120$

小数据集（9 分）

• $1 \leqslant L \leqslant R \leqslant 10^{13}$

大数据集（23 分）

• $1 \leqslant L \leqslant R \leqslant 10^{100}$

翻译由 ChatGPT-4.1 完成。