在战前，蛐蛐国利用蛐口优势，发展了很多的劳动密集型产业。但经过了连年战乱后，蛐蛐国蛐口锐减，导致工业成本大大增加，国力低迷。为此，蛐蛐国必须推进产业升级，但缺乏相应的关键技术成为了一个症结。

伏特决定用跳蚤国的高新技术——机器蚤来解决这个难题。机器蚤是一种智能化机械，可以代替跳蚤和蛐蛐进行生产工作。但操作机器蚤是一个非常复杂的工作。具体来说，每只机器蚤都有独一无二的编号——一个非空小写字符串，如果一只机器蚤 $a$ 的编号 $s_a$ 是另一只机器蚤 $b$ 的编号 $s_b$ 的子串（连续子序列），那么 $b$ 就可以被 $a$ 控制。

一组机器蚤 $a_1,a_2,\dots ,a_k$ 是一个互不相同的机器蚤序列，使得对 $\mathrm{\forall }1\le i<k$，$a_i$ 可以控制 $a_{i+1}$。对于一组这样的机器蚤，只需要一只蛐蛐操作 $a_1$，就可以同时控制里面所有机器蚤了。因此，给定若干机器蚤，将它们划分为最少数目的组就成为一个至关重要的问题。

现在伏特有一个机器蚤的命名串——一个非空小写字符串 $S$，伏特会询问你 $q$ 次，其中第 $i$ 次形如：考虑一个子串 $S[l_i,r_i]$ ，有一群机器蚤，它们的编号是这个子串的所有本质不同非空子串，那么最少能把它们划分成多少组？

输入格式

第一行两个正整数 $n,q$，分别表示 $S$ 的长度和询问次数。

接下来一行一个长度为 $n$ 的小写字符串 $S$。

接下来 $q$ 行，第 $i$ 行两个正整数 $l_i,r_i$，表示一个询问 $S[l_i,r_i]$ 。下标从 $1$ 开始。

输出格式

输出共 $q$ 行，第 $i$ 行一个正整数表示第 $i$ 次询问的答案。

样例一

input

4 1
abaa
1 4

output

3

explanation

询问 $S[1,4]=S$ ，因此所有机器蚤的编号是所有 $S$ 的非空子串，即 $a,b,aa,ab,ba,aba,baa,abaa$ 。

可以证明，最少能划分为 $3$ 个组，下面是其中一组合法方案（用编号指代机器蚤）：

第 $1$ 组： $a,aa,abaa$

第 $2$ 组： $b,ab,aba$

第 $3$ 组： $ba,baa$

样例二

input

5 5
abbab
1 2
1 3
4 5
2 5
2 4

output

2
2
2
3
2

样例三

见附加文件中 ex_partition3.in 和 ex_partition3.out 。

样例四

见附加文件中 ex_partition4.in 和 ex_partition4.out 。

数据范围

对于所有数据， $1\le n,q\le {10}^5,1\le l_i\le r_i\le n$。

时间限制：$4\mathtt{\text{s}}$

空间限制：$512\mathtt{\text{MB}}$

下载

样例数据下载