E. Тривиальная задача на строки
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
1024 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

Определим $$$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]$$$ представляет собой подстроку$$$^{\text{∗}}$$$ строки $$$s$$$ от $$$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$$$).

Вторая строка содержит строку $$$s$$$ длиной $$$n$$$, состоящую только из строчных латинских букв.

$$$i$$$-я из следующих $$$q$$$ строк содержит два целых числа $$$l_i$$$ и $$$r_i$$$ ($$$1 \le l_i \le r_i \le n$$$), описывающих $$$i$$$-й запрос.

Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$10^6$$$.

Выходные данные

Для каждого запроса выведите целое число — значение выражения.

Пример
Входные данные
6
1 1
a
1 1
5 2
aaaaa
1 5
2 4
6 2
abcdef
1 6
3 5
6 3
abaaba
1 6
1 3
2 6
7 3
abcabca
1 7
2 7
4 7
8 3
aababaac
1 8
2 8
3 7
Выходные данные
1
15
6
6
3
14
4
7
12
9
5
13
14
7
Примечание

В первом наборе входных данных $$$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$$$.