子串 = S

题目描述

共有 $T$ 个测试用例，每个测试用例给你一个由数字组成的字符串 $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)$。

输入格式

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

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

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

$S$ $L$ $R$

输出格式

共输出 $T$ 行。

第 $i$ 行输出一个整数，表示第 $i$ 个测试用例的答案。

样例

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

12
0
14888888888888889
12982260572545
10987664021
1

本输入包含 6 个测试用例。

在第一个测试用例中，$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$。

数据范围

• $1 \le T \le 1000$
• $S$ 是由数字组成的字符串，其长度介于 $1$ 和 $16$ 之间（含两端）。
• $L$ 和 $R$ 是整数，满足 $1 \le L \le R \lt 10^{16}$。