Bessie는 최근 그림 도구 세트를 받았으며, 목초지 한쪽 끝에 있는 긴 울타리에 색을 칠하려 한다. 울타리는 연속된 $N$개의 길이 1미터인 구간으로 이루어져 있다($1\le N\le 10^5$). Bessie는 서로 다른 26가지 색을 가지고 있으며, 색이 어두워지는 순서대로 'A'부터 'Z'까지의 문자로 표시한다('A'는 매우 밝은 색이고 'Z'는 매우 어두운 색이다). 따라서 각 울타리 구간에 칠하려는 색을, 각 문자가 알파벳인 길이 $N$의 문자열로 나타낼 수 있다.

처음에는 모든 울타리 구간이 칠해져 있지 않다. Bessie는 더 어두운 색 위에 더 밝은 색을 칠하지 않는 한, 임의의 연속된 구간을 한 번의 붓질로 하나의 색으로 칠할 수 있다(더 밝은 색 위에는 더 어두운 색만 칠할 수 있다).

예를 들어 처음에 칠해져 있지 않은 길이 네인 구간은 다음과 같이 칠할 수 있다.

.... -> BBB. -> BBLL -> BQQL

시간이 부족해진 Bessie는 울타리의 어떤 연속된 구간을 칠하지 않고 남겨야 할 수도 있다고 생각한다! 현재 $Q$개의 후보 구간($1\le Q\le 10^5$)을 고려하고 있다. 각각은 $1 \leq a \leq b \leq N$을 만족하는 두 정수 $(a,b)$로 나타내며, 칠하지 않고 남길 구간 $a \ldots b$의 양 끝 인덱스를 뜻한다.

각 후보 구간에 대해, 구간 안의 모든 울타리 구간을 칠하지 않은 상태로 남기면서 구간 밖의 각 울타리 구간을 원하는 색으로 칠하는 데 필요한 최소 붓질 횟수는 얼마인가? 이 과정에서 Bessie는 실제로 색을 칠하지 않으므로 각 후보 구간의 답은 독립적이다.

입력

첫째 줄에 $N$과 $Q$가 주어진다.

다음 줄에 각 울타리 구간의 원하는 색을 나타내는 길이 $N$의 문자열이 주어진다.

다음 $Q$개의 줄에는 각각 공백으로 구분된 두 정수 $a$와 $b$가 주어지며, 칠하지 않을 수도 있는 후보 구간을 나타낸다.

출력

$Q$개의 후보 각각에 대해 답을 새로운 줄에 출력한다.

예제

입력 1

8 2
ABBAABCB
3 6
1 4

출력 1

4
3

참고

이 예제에서 원하는 무늬가 $\texttt{BAAB}$인 부분 구간을 제외하면 칠하는 데 네 번의 붓질이 필요하지만, $\texttt{ABBA}$를 제외하면 세 번만 필요하다.

.... -> AA.. -> ABBB -> ABCB

서브태스크

• 테스트 케이스 1–4는 $N,Q\le 100$을 만족한다.
• 테스트 케이스 5–7은 $N,Q\le 5000$을 만족한다.
• 테스트 케이스 8–13에는 추가 제한이 없다.

출제자: Andi Qu 및 Brian Dean