Bessie ha recentemente ricevuto un set da pittura e vuole dipingere la lunga recinzione a un'estremità del suo pascolo. La recinzione è composta da $N$ segmenti consecutivi di 1 metro ($1\le N\le 10^5$). Bessie dispone di 26 colori diversi, che etichetta con le lettere da 'A' a 'Z' in ordine crescente di scurezza ('A' è molto chiaro e 'Z' molto scuro). Può quindi descrivere il colore desiderato di ogni segmento mediante una stringa di lunghezza $N$ in cui ogni carattere è una lettera.

Inizialmente, tutti i segmenti sono senza colore. Bessie può colorare qualsiasi intervallo contiguo di segmenti con un unico colore in una sola pennellata, purché non dipinga mai un colore più chiaro sopra uno più scuro (può dipingere solo colori più scuri sopra colori più chiari).

Per esempio, un segmento inizialmente senza colore di lunghezza quattro può essere colorato così:

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

Avendo poco tempo, Bessie pensa che potrebbe dover lasciare senza pittura un intervallo consecutivo di segmenti! Attualmente considera $Q$ intervalli candidati ($1\le Q\le 10^5$), ciascuno descritto da due interi $(a,b)$ con $1 \leq a \leq b \leq N$, che indicano gli indici delle estremità dell'intervallo $a \ldots b$ da lasciare senza pittura.

Per ogni intervallo candidato, qual è il numero minimo di pennellate necessario per dipingere ogni segmento esterno all'intervallo con il colore desiderato, lasciando tutti i segmenti interni senza colore? Bessie non dipinge realmente nulla durante questo processo, quindi le risposte per ogni intervallo candidato sono indipendenti.

Input

La prima riga contiene $N$ e $Q$.

La riga successiva contiene una stringa di lunghezza $N$ che rappresenta il colore desiderato per ogni segmento della recinzione.

Ciascuna delle successive $Q$ righe contiene due interi $a$ e $b$ separati da uno spazio, che rappresentano un intervallo candidato da lasciare eventualmente senza pittura.

Output

Per ciascuno dei $Q$ candidati, stampa la risposta su una nuova riga.

Esempi

Input 1

8 2
ABBAABCB
3 6
1 4

Output 1

4
3

Nota

In questo esempio, escludere il sottointervallo corrispondente al motivo desiderato $\texttt{BAAB}$ richiede quattro pennellate, mentre escludere $\texttt{ABBA}$ ne richiede soltanto tre.

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

Sottoproblemi

• I casi di test 1–4 soddisfano $N,Q\le 100$.
• I casi di test 5–7 soddisfano $N,Q\le 5000$.
• I casi di test 8–13 non hanno vincoli aggiuntivi.

Autori del problema: Andi Qu e Brian Dean