B. Непалиндромная подстрока
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Строка $$$t$$$ считается $$$k$$$-хорошей, если существует хотя бы одна подстрока$$$^\dagger$$$ длины $$$k$$$, которая не является палиндромом$$$^\ddagger$$$. Пусть $$$f(t)$$$ обозначает сумму всех значений $$$k$$$, при которых строка $$$t$$$ является $$$k$$$-хорошей.

Вам дана строка $$$s$$$ длины $$$n$$$. Вы должны ответить на $$$q$$$ следующих запросов:

  • Для данных $$$l$$$ и $$$r$$$ ($$$l < r$$$), найдите значение $$$f(s_ls_{l + 1}\ldots s_r)$$$.

$$$^\dagger$$$ Подстрока строки $$$z$$$ — это последовательность подряд идущих символов строки $$$z$$$. Например, «$$$\mathtt{defor}$$$», «$$$\mathtt{code}$$$» и «$$$\mathtt{o}$$$» являются подстроками «$$$\mathtt{codeforces}$$$», а «$$$\mathtt{codes}$$$» и «$$$\mathtt{aaa}$$$» не являются.

$$$^\ddagger$$$ Палиндром — это строка, которая одинаково читается как слева направо, так и справа налево. Например, строки «$$$\texttt{z}$$$», «$$$\texttt{aa}$$$» и «$$$\texttt{tacocat}$$$» являются палиндромами, а «$$$\texttt{codeforces}$$$» и «$$$\texttt{ab}$$$» — нет.

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

Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит одно целое число $$$t$$$ ($$$1 \leq t \leq 2 \cdot 10^4$$$) — количество наборов входных данных. Далее следует описание наборов.

Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$q$$$ ($$$2 \le n \le 2 \cdot 10^5, 1 \le q \le 2 \cdot 10^5$$$) — длину строки и количество запросов соответственно.

Вторая строка каждого набора содержит строку $$$s$$$. Гарантируется, что строка $$$s$$$ содержит только строчные латинские буквы.

Следующие $$$q$$$ строк содержат по два целых числа $$$l$$$ и $$$r$$$ ($$$1 \le l < r \le n$$$).

Гарантируется, что сумма $$$n$$$ и сумма $$$q$$$ по всем наборам входных данных не превосходят $$$2 \cdot 10^5$$$.

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

Для каждого запроса выведите $$$f(s_ls_{l + 1}\ldots s_r)$$$.

Пример
Входные данные
5
4 4
aaab
1 4
1 3
3 4
2 4
3 2
abc
1 3
1 2
5 4
pqpcc
1 5
4 5
1 3
2 4
2 1
aa
1 2
12 1
steponnopets
1 12
Выходные данные
9
0
2
5
5
2
14
0
2
5
0
65
Примечание

В первом запросе первого набора входных данных строка равняется $$$\mathtt{aaab}$$$. Подстроки $$$\mathtt{aaab}$$$, $$$\mathtt{aab}$$$ и $$$\mathtt{ab}$$$ не являются палиндромами и имеют длины $$$4$$$, $$$3$$$ и $$$2$$$ соответственно. Таким образом, строка является $$$2$$$-хорошей, $$$3$$$-хорошей и $$$4$$$-хорошей. Следовательно, $$$f(\mathtt{aaab}) = 2 + 3 + 4 = 9$$$.

Во втором запросе первого набора строка имеет вид $$$\mathtt{aaa}$$$. В ней нет непалиндромных подстрок. Следовательно, $$$f(\mathtt{aaa}) = 0$$$.

В первом запросе второго набора входных данных строка имеет вид $$$\mathtt{abc}$$$. Подстроки $$$\mathtt{ab}$$$, $$$\mathtt{bc}$$$ и $$$\mathtt{abc}$$$ не являются палиндромами и имеют длины $$$2$$$, $$$2$$$ и $$$3$$$ соответственно. Таким образом, строка является $$$2$$$-хорошей и $$$3$$$-хорошей. Следовательно, $$$f(\mathtt{abc}) = 2 + 3 = 5$$$. Заметим, что даже если существует $$$2$$$ непалиндромных подстроки длины $$$2$$$, мы считаем их только один раз.