Bessie recebeu recentemente um conjunto de pintura e quer pintar a longa cerca em uma extremidade de seu pasto. A cerca consiste em $N$ segmentos consecutivos de 1 metro ($1\le N\le 10^5$). Bessie dispõe de 26 cores diferentes, que identifica com as letras 'A' a 'Z' em ordem crescente de escuridão ('A' é uma cor muito clara e 'Z' muito escura). Assim, pode descrever a cor desejada de cada segmento como uma string de comprimento $N$ em que cada caractere é uma letra.

Inicialmente, todos os segmentos estão sem cor. Bessie pode colorir qualquer intervalo contíguo de segmentos com uma única cor em uma única pincelada, desde que nunca pinte uma cor mais clara sobre uma mais escura (só pode pintar cores mais escuras sobre cores mais claras).

Por exemplo, um segmento inicialmente sem cor de comprimento quatro pode ser colorido assim:

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

Com pouco tempo, Bessie acha que talvez precise deixar algum intervalo consecutivo de segmentos sem pintar! Atualmente considera $Q$ intervalos candidatos ($1\le Q\le 10^5$), cada um descrito por dois inteiros $(a,b)$ com $1 \leq a \leq b \leq N$, que indicam os índices das extremidades do intervalo $a \ldots b$ a deixar sem pintar.

Para cada intervalo candidato, qual é o menor número de pinceladas necessário para pintar cada segmento fora do intervalo com sua cor desejada, deixando todos os segmentos dentro dele sem cor? Observe que Bessie não faz nenhuma pintura de fato nesse processo, portanto as respostas para cada intervalo candidato são independentes.

Entrada

A primeira linha contém $N$ e $Q$.

A linha seguinte contém uma string de comprimento $N$ que representa a cor desejada de cada segmento da cerca.

Cada uma das próximas $Q$ linhas contém dois inteiros $a$ e $b$ separados por um espaço, representando um intervalo candidato que pode ser deixado sem pintar.

Saída

Para cada um dos $Q$ candidatos, imprima a resposta em uma nova linha.

Exemplos

Entrada 1

8 2
ABBAABCB
3 6
1 4

Saída 1

4
3

Explicação

Neste exemplo, excluir o subintervalo correspondente ao padrão desejado $\texttt{BAAB}$ exige quatro pinceladas para pintar, enquanto excluir $\texttt{ABBA}$ exige apenas três.

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

Subtarefas

• Os casos de teste 1–4 satisfazem $N,Q\le 100$.
• Os casos de teste 5–7 satisfazem $N,Q\le 5000$.
• Os casos de teste 8–13 não têm restrições adicionais.

Autores do problema: Andi Qu e Brian Dean