P13447 [GCJ 2009 #3] Interesting Ranges

如果一个正整数的十进制表示（不含前导零）是回文字符串（即正着读和反着读都一样），那么这个数就是回文数。例如，$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]$ 的所有有趣子区间的个数。

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

对于每组测试数据，输出一行，格式如下： Case #$x$: $y$ 其中 $x$ 表示测试编号（从 $1$ 开始），$y$ 表示 $[L, R]$ 中有趣子区间的个数，对 $1000000007$ 取模。

**限制条件** - $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 完成。