问题 B: 非 Palindromic 子串

给你一个长度为 $n$ 的字符串 $s$ 。您需要回答下列问题中的 $q$ 个：如果至少存在一个长度为 $k$ 的子串 $^\dagger$ 不是回文 $^\ddagger$ ，那么这个字符串 $t$ 可以说是 $k$ -good 的。让 $f(t)$ 表示 $k$ 的所有值的总和，使得字符串 $t$ 是 $k$ 好的。 - 给定 $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}$ "不是。 [Problem - 1943B - Codeforces ](https://codeforces.com/problemset/problem/1943/B) [CF1943B Non-Palindromic Substring - 洛谷](https://www.luogu.com.cn/problem/CF1943B)

每个测试包含多个测试用例。第一行包含一个整数 $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)$ 。

**注** 在第一个测试用例的第二个查询中，字符串为 $\mathtt{aaa}$ 。其中没有非拉丁字符串子串。因此是 $f(\mathtt{aaa}) = 0$ 。 在第一个测试用例的第一个查询中，字符串为 $\mathtt{aaab}$ 。 $\mathtt{aaab}$ 、 $\mathtt{aab}$ 和 $\mathtt{ab}$ 都不是回文子串，它们的长度分别为 $4$ 、 $3$ 和 $2$ 。因此，这个字符串是 $2$ /好， $3$ /好和 $4$ /好。因此， $f(\mathtt{aaab}) = 2 + 3 + 4 = 9$ 。 在第二个测试用例的第一次查询中，字符串为 $\mathtt{abc}$ 。 $\mathtt{ab}$ 、 $\mathtt{bc}$ 和 $\mathtt{abc}$ 都不是回文子串，它们的长度分别为 $2$ 、 $2$ 和 $3$ 。因此，字符串是 $2$ \-good 和 $3$ /good。因此， $f(\mathtt{abc}) = 2 + 3 = 5$ 。请注意，即使长度为 $2$ 的非醛类子串有 $2$ 个，我们也只计算一次。