如果一个正整数的十进制表示（不含前导零）是一个回文串（即正读和反读都相同的字符串），则称其为回文数。例如，5、77、363、4884、11111、12121 和 349943 都是回文数。

如果一个整数区间包含偶数个回文数，则称该区间是有趣的。区间 $[L, R]$（其中 $L \le R$）定义为从 $L$ 到 $R$ 的整数序列：$(L, L+1, L+2, \dots, R-1, R)$。$L$ 和 $R$ 分别是该区间的起始数和结束数。

如果 $L \le L_1 \le R_1 \le R$，则称区间 $[L_1, R_1]$ 是 $[L, R]$ 的一个子区间。你的任务是确定 $[L, R]$ 中有多少个有趣的子区间。

输入格式

输入的第一行包含测试用例的数量 $T$。接下来有 $T$ 个测试用例。每个测试用例占一行，包含两个正整数 $L$ 和 $R$（按此顺序），中间用空格隔开。

输出格式

对于每个测试用例，输出一行。该行应包含 "Case #x: y"，其中 $x$ 是从 1 开始的用例编号，$y$ 是 $[L, R]$ 中有趣的子区间的数量，结果对 $1000000007$ 取模。

数据范围

$1 \le T \le 120$

小数据

$1 \le L \le R \le 10^{13}$

大数据

$1 \le L \le R \le 10^{100}$

样例

样例输入 1

3
1 2
1 7
12 110

样例输出 1

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