背景

7unar 曾经写过很多东西。有些已经记不清顺序，有些当时认为无比重要的，如今再看似乎也没有那么重要。

他把过去写下的一些文字交给了 AI。AI 并没有试图理解那些文字，只是把每一个阶段的 7unar 映射成一个小写字母。于是，一段复杂的过去，被压缩成了一串冰冷的字符串 $s = s_1 s_2 \cdots s_n$。

描述

7unar 给出了 $q$ 次查询。每次查询给出两个整数 $l, r$，表示只考虑时间序列中的第 $l$ 到第 $r$ 个阶段，即子串 $s[l, r]$。

请你告诉他：在这一段过去中，出现次数最多的子串，究竟出现了多少次。

形式化的：子串是 $s$ 中连续且顺序一致的一段。对 $s[l, r]$ 的任意子串 $t$，记 $cnt(t)$ 为 $t$ 在 $s[l, r]$ 中出现的次数，求 $\max cnt(t)$。

“历史不是过去；历史是被现在历史化了的过去。”7unar 当然知道这一点。但他还是想知道——在那些已经无法重新经历的时间里，有没有什么东西一直重复着。

输入格式

第一行两个整数 $n, q$，分别表示字符串长度和查询次数。

第二行一个仅由小写字母组成的字符串 $s$。

接下来 $q$ 行，每行两个整数 $l, r$，表示一次查询。

输出格式

输出 $q$ 行，每行一个整数，表示对应查询中 $s[l, r]$ 出现次数最多的子串的出现次数。

样例

输入数据 1

8 3
abacabad
1 8
2 4
1 3

输出数据 1

4
1
2

输入数据 2

6 1
banana
1 6

输出数据 2

3

限制

对于 $100\%$ 的数据，$1 \le n, q \le 10^6$，$1 \le l \le r \le n$，$s$ 仅由小写字母组成。