CFCF2209E.A Trivial String Problem

定义 $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$ 个字符（包括两端）构成的子串 $^{\ast}$。你需要回答 $q$ 个询问。对于第 $i$ 个询问，给出两个整数 $l_i$ 和 $r_i$，你需要求出：

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

$^{\ast}$ 如果字符串 $a$ 可以通过从字符串 $b$ 的开头删除若干（可以为 $0$ 或全部）字符以及从结尾删除若干（可以为 $0$ 或全部）字符得到，则称 $a$ 是 $b$ 的子串。

每组测试数据包含多组用例。第一行包含一个整数 $t$（$1 \le t \le 10^3$），表示用例数。

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

第二行给出长度为 $n$ 的字符串 $s$，只包含小写英文字母。

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

保证所有用例中 $n$ 的总和不超过 $10^6$。

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

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