Bessie ha recibido recientemente un juego de pintura y quiere pintar la larga cerca en un extremo de su pastizal. La cerca consta de $N$ segmentos consecutivos de 1 metro ($1\le N\le 10^5$). Bessie dispone de 26 colores distintos, que etiqueta con las letras 'A' a 'Z' en orden creciente de oscuridad ('A' es muy claro y 'Z' muy oscuro). Por tanto, puede describir el color deseado de cada segmento mediante una cadena de longitud $N$ donde cada carácter es una letra.

Inicialmente, todos los segmentos están sin colorear. Bessie puede colorear cualquier intervalo contiguo de segmentos con un único color mediante una sola pincelada, siempre que nunca pinte un color más claro sobre uno más oscuro (solo puede pintar colores más oscuros sobre otros más claros).

Por ejemplo, un segmento inicialmente sin colorear de longitud cuatro puede pintarse así:

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

Como le queda poco tiempo, ¡Bessie cree que quizá deba dejar sin pintar algún intervalo consecutivo de segmentos! Actualmente considera $Q$ intervalos candidatos ($1\le Q\le 10^5$), cada uno descrito por dos enteros $(a,b)$ con $1 \leq a \leq b \leq N$, que dan los índices de los extremos del intervalo $a \ldots b$ que se dejará sin pintar.

Para cada intervalo candidato, ¿cuál es el mínimo número de pinceladas necesarias para pintar cada segmento exterior al intervalo con su color deseado, dejando todos los segmentos interiores sin colorear? Bessie no realiza ninguna pintura durante este proceso, por lo que las respuestas de cada intervalo candidato son independientes.

Entrada

La primera línea contiene $N$ y $Q$.

La siguiente línea contiene una cadena de longitud $N$ que representa el color deseado de cada segmento de la cerca.

Cada una de las siguientes $Q$ líneas contiene dos enteros $a$ y $b$ separados por un espacio, que representan un intervalo candidato que posiblemente se deje sin pintar.

Salida

Para cada uno de los $Q$ candidatos, imprime la respuesta en una línea nueva.

Ejemplos

Entrada 1

8 2
ABBAABCB
3 6
1 4

Salida 1

4
3

Nota

En este ejemplo, excluir el subintervalo correspondiente al patrón deseado $\texttt{BAAB}$ requiere cuatro pinceladas para pintar, mientras que excluir $\texttt{ABBA}$ requiere solo tres.

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

Subtareas

• Los casos de prueba 1–4 satisfacen $N,Q\le 100$.
• Los casos de prueba 5–7 satisfacen $N,Q\le 5000$.
• Los casos de prueba 8–13 no tienen restricciones adicionales.

Autores del problema: Andi Qu y Brian Dean