一个字符串$t$是字符串$s$的half border，当且仅当$t$是$s$的前缀，也是$s$的后缀，并且它们出现位置不重叠（也就是说$2|t| \le |s|$）。
现在你有一个长度为$n$的字符串$s$，定义字符串$S(i,j)$ ($1 \le i \le j \le n$)是把字符串$s$第$i$个到第$j$个全部删掉后得到的字符串。也就是说$S(i,j)=s_{1..i-1} \oplus s_{j + 1..n}$，其中$\oplus$表示字符串连接操作，$s_{i..j}$表示$s$从第$i$个位置到第$j$个位置的子串。
给出$m$个询问，每次给出$l,r$，求出$\text{HBS}(l,r)$，表示$S(l,r)$的所有half border的长度之和。
输入有多组数据。第一行有一个整数$T$，表示测试数据组数。然后对于每组数据：
第一行包含$2$个整数$n$和$m$ ($1 \le n,m \le 5 \times 10^5$)，表示字符串长度和询问个数。
第二行包含一个长度为$n$的字符串$s$，保证$s$仅由英语小写字母组成。
接下来$m$行，每行包含$2$个整数$l$和$r$ ($1 \le l \le r \le n$)，表示一个询问。
保证所有数据中$n$的和或者$m$的和都不超过$5 \times 10^5$。
对于每组询问，输出一个整数表示$\text{HBS}(l,r)$。
1 21 18 abaababaabaababaababa 18 18 12 12 10 19 13 15 12 20 7 8 4 11 1 16 7 9 18 20 1 16 9 18 3 16 12 14 1 14 5 10 7 19 10 18
4 12 4 4 5 4 4 1 12 1 1 4 4 12 2 4 4 4
Comet OJ