【题目背景】

「他们说这就是人生 试着体会试着忍住眼泪 还是躲不开应该有的情绪」

闪着蓝光的绿色轻轨电车就这样驶过，就这样错过。

一晃便已成为了遥远的过去啊。哪怕时过境迁，大家也都跟反复提过那时应该是多么美好。只是，我想长崎素世小姐说的恐怕是对的吧，「我们早已回不到当初。」我们的社交圈子也早就彻彻底底地变了，回到曾经要付出代价绝对不会小吧！

世界绝不会为我们的改变而停下转动，所以我当然也要继续向前看、向前走。但只要闲了下来，还是会情不自禁地追忆起那时啊。

【题目描述】

嘉陵江畔，小 s、小 f 和我曾玩过一个字符串游戏。

我们有一个小写英文字符串 $S$，三个人可以以任意顺序操作字符串，但要求 $S$ 始终非空。

小 s 操作时会删除 $S$ 的第一个字符，小 f 操作时会删除 $S$ 的第 $|S|$ 个字符，而我可以选择一个真后缀 $T$ 满足它也是 $S$ 反串的真后缀，将 $S$ 变为 $T$。

我觉得我的操作很酷，所以我想要最大化我的操作次数。

因为我们$\color{white}\text{曾}$是命运共同体，所以小 s 和小 f 也愿意帮助我最大化操作次数。

作为 E 队爷的小 s 和小 f 显然都是充分聪明的，只可惜我不太聪明。

于是我想要请教你，如果能回到当初，我也最优化我的操作，我会进行多少次操作呢？

考虑到这已经是遥远的过去 $\color{white}{(2024.1.25)}$，初始的 $S$ 已模糊不清。

于是我给你一个小写字符串 $T$，向你询问 $q$ 次：如果当初的 $S=T[l_i,r_i]$ ，我的最大操作次数会是多少？

【输入格式】

从文件 recall.in 中读入数据。

第一行两个整数 $c,q$ 表示子任务编号和询问次数。样例满足 $c=0$。

第二行一个小写字符串 $S$。

接下来 $q$ 行，第 $i(1\leq i\leq q)$ 行两个整数 $l_i,r_i$ 表示询问。

【输出格式】

输出到文件 recall.out 中。

共 $q$ 行，每行一个整数表示该次询问的答案。

【样例 $1$ 输入】

0 3
aaaabbaabba
1 4
4 11
4 5

【样例 $1$ 输出】

3
4
0

【样例 $2$ 输入】

0 10
hbbhbhhbbh
1 10
6 7
2 8
9 10
7 8
6 7
8 8
9 10
3 8
2 3

【样例 $2$ 输出】

3
1
2
0
0
1
0
0
2
1

【样例 $3$】

见选手目录下的 recall/recall3.in 与 recall/recall3.ans。

这个样例满足子任务 $1$ 的约束条件。

【样例 $4$】

见选手目录下的 recall/recall4.in 与 recall/recall4.ans。

这个样例满足子任务 $4$ 的约束条件，且满足 $l_1=1,r_1=\lvert S\rvert$。

【样例 $5$】

见选手目录下的 recall/recall5.in 与 recall/recall5.ans。

这个样例满足子任务 $4$ 的约束条件，且满足 $l_1=1,r_1=\lvert S\rvert$。

【数据范围】

本题采用子任务捆绑：仅有通过该子任务内所有测试点才可以获得全分。

对于所有数据，

• $1\leq \lvert S\rvert,q\leq 10^5$，
• $S$ 中仅包含小写字母，
• $\forall 1\leq i\leq q$，$1\leq l_i\leq r_i\leq \lvert S\rvert$。

子任务编号	$\lvert S\rvert\leq$	$q\leq$	特殊性质	分值
$1$	$10^3$		无	$12$
$2$	$10^5$	$10^5$	A	$8$
$3$		$1$	B	$44$
$4$		$10^5$	无	$36$

• 特殊性质 A：$\forall 1\leq i<\lvert S\rvert$，$s_i=s_{i+1}$。

• 特殊性质 B：$\forall 1\leq i\leq q$，$l_i=1,r_i=\lvert S\rvert$。

子任务编号	$\lvert S\rvert\leq$	$q\leq$	特殊性质	分值
1	$10^3$	$10^3$	无	$12$
2	$10^5$	$10^5$	A	$8$
3	$10^5$	$1$	B	$44$
4	$10^5$	$10^5$	无	$36$