[ZJOI2020] 字符串

3s，512MB

Bob 喜欢字符串。 Bob 觉得，重复两遍的字符串是优美的，例如，`aa`，`sese`，`abcabc`，`baabaa`，`abababab`是优 美的串，而 `ab`，`aadead`，`sesese`，`abba` 不是。更具体地说，如果一个字符串 $S$ 能够被写成两个相同的字符串前后拼接的形式，即存在字符串 $P$ 使得 $S=PP$，那么 $S$ 就是优美的。 Bob 有一个长度为 $n$ 的字符串 $T=T_1T_2 \cdots T_n$。现在他想知道，给定 $T$ 的一个子串 $Q=T[l \cdots r]$，这个子串 $Q$ 内一共包含多少种本质不同的优美的串作为子串。如果两个串相同，但是出现的位置不同，那么这两个串不是本质不同。 Bob 一共有 $q$ 组不同的询问，你需要快速计算出答案。

第一行输入两个整数 $n, q$。第二行输入一个只包含小写字母 $a$ 和 $b$ 的字符串 $T$。 接下来 $q$ 行，每行输入两个整数 $l, r$，表示一组询问。

输出 $q$ 行，每行一个整数表示答案。

11 5
aabaabaaaab
1 11
1 6
7 10
5 5
3 8

5
2
2
0
2

样例解释 $1$： $|T|$ 有 `aa`，`aaaa`，`abaaba`，`aabaab`，`baabaa` 这些本质不同的优美的串。 样例输入输出 2 见附件。 对于前 $10\%$ 的数据，$n \leq 100$。 对于前 $20\%$ 的数据，$n \leq 500$。 对于前 $40\%$ 的数据，$n \leq 5000$。 对于另外 $20\%$ 的数据，保证 $T$ 中所有的优美的串的个数不超过 $10^6$，这里位置不同的串被视为不同的。 对于另外 $20\%$ 的数据，$q = 1$。 对于 $100\%$ 的数据，$1 \leq n, q \leq 200000,1 \leq l \leq r \leq n$，$T$ 只包含小写字母 `a` 和 `b`。