题目描述

传间百年前，一名侠客在雪山风雪之中救下一只奄奄一息的白狐，临走时留下一只酱板鸭，预备给狐狸充饥。

侠客本以为将来会有狐仙前来报恩，可多年后登门寻仇的，不是白狐，正是那只被遗忘在雪原、熬过寒冬的酱板鸭精。

酱板鸭精带走了侠客写下的一卷雪山密信，将完整密信整理为长度 $n$ 的小写字母字符串 $s$。

密信暗藏玄机：信中频繁重复出现的字符片段，代表精怪力量流动的痕迹。

给定一个长度为 $n$ 的字符串 $s$（仅由小写字母组成，下标从 $1$ 开始），进行 $q$ 次询问，每次询问给出两个整数 $l, r$，询问子串 $s[l..r]$ 中出现次数最多的子串出现了多少次。

注：字符串 $s$ 的子串定义为 $s$ 中连续且顺序一致的一段字符序列，即对于下标 $1 \le l \le r \le |s|$，子串 $s[l..r]$ 表示为 $s_l s_{l+1} \dots s_r$。询问时统计的是该子串在 $s[l..r]$ 内部的出现次数（允许重叠）。

输入格式

第一行输入两个整数 $n, q$（$1 \le n, q \le 100$）——分别表示字符串长度和查询次数。

第二行输入一个字符串 $s$，仅由小写字母组成。接下来 $q$ 行，每行两个整数 $l, r$（$1 \le l \le r \le n$）——表示查询子串的下标。

输出格式

对于每个询问，输出一行一个整数，表示出现次数最多的子串出现了多少次。

5 2
ababa
1 4
4 5

2
1

22 2
kskblzdjdwkzkblwmpwzmp
1 22
1 3

4
2

样例解释

第一个样例中查询 $s[1..4] = \texttt{abab}$，子串 $\texttt{ab}$ 与 $\texttt{ba}$ 都出现了 $2$ 次，是出现次数最多的子串，故输出 $2$；查询 $s[4..5] = \texttt{ba}$，两个字符互不相同，任意子串最多出现 $1$ 次，故输出 $1$。

第二个样例中查询整个字符串，单个字符 $\texttt{z}$ 在位置 $7,13,17,21$ 共出现 $4$ 次，是出现次数最多的子串，故输出 $4$；查询 $s[1..3] = \texttt{ksk}$ 时，字符 $\texttt{k}$ 出现 $2$ 次，故输出 $2$。