CF2209E.A Trivial String Problem

Define $f(t)$ as the maximum number of parts $t$ can be split into such that each part is a non-empty prefix of $t$. In other words, $f(t)$ is the maximum positive integer $k$ that satisfies the following condition:

• There exist $k$ strings $p_1,p_2,\ldots,p_k$, which are prefixes of $t$, such that $t=p_1+p_2+\ldots+p_k$. Here $+$ denotes the string concatenation.

You are given a string $s$ of length $n$, consisting of only lowercase English letters. Let $s[x..y]$ represent the substring$^{\text{∗}}$ of $s$ from the $x$-th to the $y$-th character (inclusive). You need to answer $q$ queries. The $i$-th query provides two integers $l_i$ and $r_i$, and you need to find

\\sum\_{j=l\_i}^{r\_i} f(s\[l\_i..j\]).

$^{\text{∗}}$A string $a$ is a substring of a string $b$ if $a$ can be obtained from $b$ by the deletion of several (possibly, zero or all) characters from the beginning and several (possibly, zero or all) characters from the end.

定义 $f(t)$ 为字符串 $t$ 可被划分成的最多部分数，使得每一部分均为 $t$ 的非空前缀。换言之，$f(t)$ 是满足以下条件的最大正整数 $k$：

• 存在 $k$ 个字符串 $p_1,p_2,\ldots,p_k$，它们均为 $t$ 的前缀，且满足 $t=p_1+p_2+\ldots+p_k$。其中 $+$ 表示字符串连接运算。

给定一个长度为 $n$ 的字符串 $s$，其仅由小写英文字母组成。记 $s[x..y]$ 表示 $s$ 中从第 $x$ 个字符到第 $y$ 个字符（含端点）的子串$^{\text{∗}}$。你需要回答 $q$ 个查询。第 $i$ 个查询给出两个整数 $l_i$ 和 $r_i$，你需要计算

$$\sum_{j=l_i}^{r_i} f(s[l_i..j]).$$

$^{\text{∗}}$ 若字符串 $a$ 可通过从字符串 $b$ 的开头删除若干（可能为零或全部）字符、并从结尾删除若干（可能为零或全部）字符而得到，则称 $a$ 是 $b$ 的子串。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^3$). The description of the test cases follows.

The first line of each test case contains two integers $n$ and $q$ ($1 \le n \le 10^6$, $1 \le q \le 100$).

The second line contains the string $s$ of length $n$, consisting of only lowercase English letters.

The $i$-th of the next $q$ lines contains two integers $l_i$ and $r_i$ ($1 \le l_i \le r_i \le n$), representing the $i$-th query.

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^6$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^3$）。随后是各测试用例的描述。

每个测试用例的第一行包含两个整数 $n$ 和 $q$（$1 \le n \le 10^6$，$1 \le q \le 100$）。

第二行包含一个长度为 $n$ 的字符串 $s$，仅由小写英文字母组成。

接下来的 $q$ 行中，第 $i$ 行包含两个整数 $l_i$ 和 $r_i$（$1 \le l_i \le r_i \le n$），表示第 $i$ 个查询。

保证所有测试用例的 $n$ 之和不超过 $10^6$。

For each query, output an integer representing the value of the expression.

对于每个查询，输出一个整数，表示该表达式的值。

In the first test case, $f(\texttt{a})=1$.

In the second test case, $f(\texttt{a})+f(\texttt{aa})+f(\texttt{aaa})+f(\texttt{aaaa})+f(\texttt{aaaaa})=1+2+3+4+5=15$ and $f(\texttt{a})+f(\texttt{aa})+f(\texttt{aaa})=1+2+3=6$.

In the third test case, $f(\texttt{a})+f(\texttt{ab})+f(\texttt{abc})+f(\texttt{abcd})+f(\texttt{abcde})+f(\texttt{abcdef})=1+1+1+1+1+1=6$ and $f(\texttt{c})+f(\texttt{cd})+f(\texttt{cde})=1+1+1=3$.

在第一个测试用例中，$f(\texttt{a})=1$。

在第二个测试用例中，$f(\texttt{a})+f(\texttt{aa})+f(\texttt{aaa})+f(\texttt{aaaa})+f(\texttt{aaaaa})=1+2+3+4+5=15$，且 $f(\texttt{a})+f(\texttt{aa})+f(\texttt{aaa})=1+2+3=6$。

在第三个测试用例中，$f(\texttt{a})+f(\texttt{ab})+f(\texttt{abc})+f(\texttt{abcd})+f(\texttt{abcde})+f(\texttt{abcdef})=1+1+1+1+1+1=6$，且 $f(\texttt{c})+f(\texttt{cd})+f(\texttt{cde})=1+1+1=3$。