{"problem":{"name":"substr = S","description":{"content":"You are given a string $S$ consisting of digits and positive integers $L$ and $R$ for each of $T$ test cases. Solve the following problem. For a positive integer $x$, let us define $f(x)$ as the numbe","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":4000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc295_f"},"statements":[{"statement_type":"Markdown","content":"You are given a string $S$ consisting of digits and positive integers $L$ and $R$ for each of $T$ test cases. Solve the following problem.\nFor a positive integer $x$, let us define $f(x)$ as the number of contiguous substrings of the decimal representation of $x$ (without leading zeros) that equal $S$.\nFor instance, if $S=$ `22`, we have $f(122) = 1$, $f(123) = 0$, $f(226) = 1$, and $f(222) = 2$.\nFind $\\displaystyle \\sum_{k=L}^{R} f(k)$.\n\n## Constraints\n\n*   $1 \\le T \\le 1000$\n*   $S$ is a string consisting of digits whose length is between $1$ and $16$, inclusive.\n*   $L$ and $R$ are integers satisfying $1 \\le L \\le R < 10^{16}$.\n\n## Input\n\nThe input is given from Standard Input in the following format, where $\\rm{case}_i$ denotes the $i$\\-th test case:\n\n$T$\n$\\rm{case}_{1}$\n$\\rm{case}_{2}$\n$\\vdots$\n$\\rm{case}_{\\it{T}}$\n\nEach test case is in the following format:\n\n$S$ $L$ $R$\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"对于每个测试用例，给定一个由数字组成的字符串 $S$ 以及两个正整数 $L$ 和 $R$。请解决以下问题：\n对于正整数 $x$，定义 $f(x)$ 为 $x$ 的十进制表示（不含前导零）中等于 $S$ 的连续子串的个数。\n例如，若 $S=$ `22`，则有 $f(122) = 1$，$f(123) = 0$，$f(226) = 1$，$f(222) = 2$。\n求 $\\displaystyle \\sum_{k=L}^{R} f(k)$。\n\n## Constraints\n\n*   $1 \\le T \\le 1000$\n*   $S$ 是由数字组成的字符串，长度在 $1$ 到 $16$ 之间（含）。\n*   $L$ 和 $R$ 是满足 $1 \\le L \\le R < 10^{16}$ 的整数。\n\n## Input\n\n输入从标准输入按以下格式给出，其中 $\\rm{case}_i$ 表示第 $i$ 个测试用例：\n\n$T$\n$\\rm{case}_{1}$\n$\\rm{case}_{2}$\n$\\vdots$\n$\\rm{case}_{\\it{T}}$\n\n每个测试用例的格式如下：\n\n$S$ $L$ $R$\n\n[samples]","is_translate":true,"language":"Chinese"}],"meta":{"iden":"abc295_f","tags":[],"sample_group":[["6\n22 23 234\n0295 295 295\n0 1 9999999999999999\n2718 998244353 9982443530000000\n869120 1234567890123456 2345678901234567\n2023032520230325 1 9999999999999999","12\n0\n14888888888888889\n12982260572545\n10987664021\n1\n\nThis input contains six test cases.\n\n*   In the first test case, $S=$ `22`, $L=23$, $R=234$.\n    *   $f(122)=f(220)=f(221)=f(223)=f(224)=\\dots=f(229)=1$.\n    *   $f(222)=2$.\n    *   Thus, the answer is $12$.\n*   In the second test case, $S=$ `0295`, $L=295$, $R=295$.\n    *   Note that $f(295)=0$."]],"created_at":"2026-03-03 11:01:14"}}