Bessie hat kürzlich ein Malset bekommen und möchte den langen Zaun an einem Ende ihrer Weide streichen. Der Zaun besteht aus $N$ aufeinanderfolgenden, 1 Meter langen Abschnitten ($1\le N\le 10^5$). Bessie hat 26 verschiedene Farben, die sie in zunehmender Dunkelheit mit den Buchstaben 'A' bis 'Z' bezeichnet ('A' ist sehr hell, 'Z' sehr dunkel). Daher kann sie die gewünschte Farbe jedes Zaunabschnitts durch eine Zeichenkette der Länge $N$ beschreiben, deren Zeichen jeweils Buchstaben sind.

Anfangs sind alle Abschnitte unbemalt. Bessie kann jeden zusammenhängenden Bereich von Abschnitten mit einem einzigen Pinselstrich in einer einzigen Farbe streichen, solange sie niemals eine hellere über eine dunklere Farbe streicht (sie kann nur dunklere Farben über hellere streichen).

Zum Beispiel lässt sich ein anfangs unbemalter Abschnitt der Länge vier wie folgt färben:

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

Da die Zeit knapp wird, denkt Bessie, dass sie vielleicht einen zusammenhängenden Bereich von Zaunabschnitten unbemalt lassen muss! Derzeit betrachtet sie $Q$ mögliche Bereiche ($1\le Q\le 10^5$), jeweils beschrieben durch zwei ganze Zahlen $(a,b)$ mit $1 \leq a \leq b \leq N$. Diese geben die Indizes der Endpunkte des Bereichs $a \ldots b$ an, der unbemalt bleiben soll.

Wie viele Pinselstriche sind für jeden möglichen Bereich mindestens nötig, um jeden Zaunabschnitt außerhalb des Bereichs in seiner gewünschten Farbe zu streichen und alle Abschnitte innerhalb unbemalt zu lassen? Bessie streicht während dieses Prozesses tatsächlich nichts, daher sind die Antworten für die möglichen Bereiche unabhängig.

Eingabe

Die erste Zeile enthält $N$ und $Q$.

Die nächste Zeile enthält eine Zeichenkette der Länge $N$, die die gewünschte Farbe jedes Zaunabschnitts angibt.

Jede der nächsten $Q$ Zeilen enthält zwei durch ein Leerzeichen getrennte ganze Zahlen $a$ und $b$, die einen möglichen Bereich beschreiben, der eventuell unbemalt bleibt.

Ausgabe

Gib für jeden der $Q$ Kandidaten die Antwort in einer neuen Zeile aus.

Beispiele

Eingabe 1

8 2
ABBAABCB
3 6
1 4

Ausgabe 1

4
3

Hinweis

In diesem Beispiel erfordert das Auslassen des Teilbereichs mit dem gewünschten Muster $\texttt{BAAB}$ vier Pinselstriche zum Streichen, während das Auslassen von $\texttt{ABBA}$ nur drei erfordert.

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

Teilaufgaben

• Die Testfälle 1–4 erfüllen $N,Q\le 100$.
• Die Testfälle 5–7 erfüllen $N,Q\le 5000$.
• Die Testfälle 8–13 haben keine zusätzlichen Beschränkungen.

Autoren der Aufgabe: Andi Qu und Brian Dean