题目描述

给定一个字符串$S$，其中包含了每个测试用例的正整数$L$和$R$。解决以下问题。

对于正整数$x$，定义$f(x)$为$x$的十进制表示的连续子字符串（不包括前导零）中等于$S$的个数。

例如，如果$S=$ 22，我们有$f(122) = 1$，$f(123) = 0$，$f(226) = 1$，以及$f(222) = 2$。

求$\\displaystyle \\sum_{k=L}^{R} f(k)$。

约束条件

• $1 \\le T \\le 1000$
• $S$是一个由数字组成的字符串，长度在$1$到$16$之间。
• $L$和$R$是满足$1 \\le L \\le R < 10^{16}$的整数。

输入

输入以以下格式从标准输入给出，其中$\\rm{case}_i$表示第$i$个测试用例：

$T$ $\\rm{case}_{1}$ $\\rm{case}_{2}$ $\\vdots$ $\\rm{case}_{\\it{T}}$

每个测试用例的格式如下：

$S$ $L$ $R$

输出

共打印$T$行。
第$i$行应该包含一个整数，表示第$i$个测试用例的答案。

示例输入 1

6
22 23 234
0295 295 295
0 1 9999999999999999
2718 998244353 9982443530000000
869120 1234567890123456 2345678901234567
2023032520230325 1 9999999999999999

示例输出 1

12
0
14888888888888889
12982260572545
10987664021
1

该输入包含六个测试用例。

• 在第一个测试用例中，$S=$ 22，$L=23$，$R=234$。
  • $f(122)=f(220)=f(221)=f(223)=f(224)=\\dots=f(229)=1$。
  • $f(222)=2$。
  • 因此，答案是$12$。
• 在第二个测试用例中，$S=$ 0295，$L=295$，$R=295$。
  • 注意$f(295)=0$。