AT_abc295_f [ABC295F] substr = 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}_T$ 每个测试用例格式如下： > $S$ $L$ $R$

请输出共 $T$ 行。 第 $i$ 行输出第 $i$ 个测试用例的答案，结果为整数。

### 限制 - $1 \leq T \leq 1000$ - $S$ 是长度在 $1$ 到 $16$ 之间的仅由数字组成的字符串 - $L,R$ 满足 $1 \leq L \leq R < 10^{16}$ ### 样例解释 1 该输入包含 $6$ 个测试用例。 - 第 $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$。 - 第 $2$ 个用例为 $S=0295$，$L=295$，$R=295$。 - 注意 $f(295)=0$。 由 ChatGPT 4.1 翻译