No Time to Paint

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

처음에는 모든 울타리 구간이 칠해지지 않은 상태이다. Bessie는 밝은 색 위에 어두운 색만 칠할 수 있다는 조건을 지키는 한, 한 번의 붓질로 연속한 구간을 한 가지 색으로 칠할 수 있다.

예를 들어, 처음에 칠해지지 않은 길이 4인 구간은 다음과 같이 칠할 수 있다:

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

시간이 부족한 Bessie는 연속한 일부 구간을 칠하지 않고 남겨 두어야 할지도 모른다고 생각한다. 현재 $Q$개의 후보 구간을 고려하고 있으며 ($1\le Q\le 10^5$), 각 후보 구간은 두 정수 $(a,b)$로 주어진다. 여기서 $1 \leq a \leq b \leq N$이고, $a \ldots b$ 구간의 양 끝 구간 번호를 나타낸다.

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

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

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

다음 $Q$개 줄에 각각 후보 구간을 나타내는 두 정수 $a$와 $b$가 공백으로 구분되어 주어진다.

각 후보 구간에 대해 답을 한 줄에 하나씩 출력한다.