울타리 색칠하기

전업주부인 윈터는 최근 지인에게 페인트 세트를 선물 받았습니다. 그녀는 자신의 전원 주택 한쪽 끝에 위치한 긴 울타리에 페인트를 칠하고 싶어합니다. 

울타리는 $N$개의 1m 구간으로 나뉘어져있습니다 ($1 \le N \le 10^5$). 

윈터는 'A'부터 'Z'까지의 26가지 서로 다른 색깔의 페인트가 있습니다. 이 색들은 밝은 순서로 배열되어있으며 'A'는 매우 밝은 색이고, 'Z'는 매우 어두운 색입니다. 

각 울타리 구간에 칠하려는 색을 길이가 $N$인 문자열로 표현할 수 있습니다.

처음에 모든 울타리 구간은 칠해지지 않은 상태입니다. 

윈터는 한 번의 붓질로 연속된 구간에 하나의 색을 칠할 수 있으나 더 밝은 색상은 더 어두운 색상 위에 칠할 수 없습니다. 반대로, 더 어두운 색상은 더 밝은 색상 위에 칠할 수 있습니다.

예를 들어, 아래와 같이 처음에 색이 칠해지지 않은 네 개의 울타리 구간을 다음과 같이 칠할 수 있습니다:

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

시간 관계상, 윈터는 일부 울타리 구간을 칠하지 않고 남겨둬야 할 상황입니다. 현재 그녀는 $Q$개의 도안을 준비하여, 어떤 구간을 색칠할지 고민 중입니다.($1 \le Q \le 10^5$)

 각 도안의 범위는 두 정수 $(a,b)$로 주어지며, $1 \leq a \leq b \leq N$의 조건을 만족합니다.

a와 b는 구간의 시작점과 끝점 인덱스를 나타냅니다. 이 범위에 속하는 구간은 칠하지 않고 남겨두어야 합니다. 

각 도안 범위에 대해, 해당 범위 내의 울타리 구간은 칠하지 않고, 그 외의 모든 구간은 원하는 색깔로 칠하려면 최소 몇 번의 붓질이 필요할까요? (윈터는 이 과정에서 실제로 붓질을 하지 않으므로, 각 도안의 범위에 대한 답변은 독립적입니다.)

첫 번째 줄은 $N$과 $Q$를 포함합니다.

다음 줄에는 각 울타리 구간에 대해 원하는 색을 나타내는 길이 $N$의 문자열이 포함됩니다.

다음 $Q$줄은 각각 두 개의 공백으로 구분된 정수 $a$와 $b$를 포함합니다. 이는 색칠하지 않는 도안의 범위를 나타냅니다.

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