A16867 | 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$。

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