将$$$f(t)$$$定义为$$$t$$$可以分割成的最大部分数,使得每个部分都是$$$t$$$的非空前缀。换句话说,$$$f(t)$$$是满足以下条件的最大正整数$$$k$$$:
- 存在$$$k$$$字符串$$$p_1,p_2,\ldots,p_k$$$,它们是$$$t$$$的前缀,使得$$$t=p_1+p_2+\ldots+p_k$$$。这里$$$+$$$表示字符串连接。
给定一个字符串 $$$s$$$,长度为 $$$n$$$,仅包含小写英文字母。设 $$$s[x..y]$$$ 表示 $$$s$$$ 的子串 $$$^{\text{∗}}$$$ 从第 $$$x$$$ 到第 $$$y$$$ 个字符(含)。您需要回答 $$$q$$$ 查询。第 $$$i$$$ 查询提供了两个整数 $$$l_i$$$ 和 $$$r_i$$$,你需要找到
$$\sum_{j=l_i}^{r_i} f(s[l_i..j]).$$
$$$^{\text{*}}$$$ 字符串 $$$a$$$ 是字符串 $$$b$$$ 的子字符串,如果 $$$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$$$ 行的第 $$$i$$$ 行包含两个整数 $$$l_i$$$ 和 $$$r_i$$$ ($$$1 \le l_i \le r_i \le n$$$),表示第 $$$i$$$ 查询。
保证所有测试用例的$$$n$$$总和不超过$$$10^6$$$。
输出
对于每个查询,输出一个表示表达式值的整数。
示例
输入复制
61 1a1 15 2aaaaa1 52 46 2abcdef1 63 56 3abaaba1 61 32 67 3abcabca1 72 74 78 3aababaac1 82 83 7
输出复制
1156631447129513147
注意
在第一个测试用例中,$$$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$$$。