Bessie niedawno otrzymała zestaw do malowania i chce pomalować długi płot na jednym końcu swojego pastwiska. Płot składa się z $N$ kolejnych odcinków długości 1 metra ($1\le N\le 10^5$). Bessie ma do dyspozycji 26 różnych kolorów, oznaczonych literami od 'A' do 'Z' w kolejności od najjaśniejszego do najciemniejszego ('A' jest bardzo jasny, a 'Z' bardzo ciemny). Może więc opisać pożądany kolor każdego odcinka napisem długości $N$, którego każdy znak jest literą.

Początkowo wszystkie odcinki są niepomalowane. Bessie może jednym pociągnięciem pędzla pomalować dowolny spójny zakres odcinków jednym kolorem, pod warunkiem że nigdy nie nałoży jaśniejszego koloru na ciemniejszy (może nakładać tylko ciemniejsze kolory na jaśniejsze).

Na przykład początkowo niepomalowany odcinek długości cztery można pokolorować tak:

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

Mając mało czasu, Bessie sądzi, że może musieć pozostawić pewien ciągły zakres odcinków płotu niepomalowany! Obecnie rozważa $Q$ zakresów kandydatów ($1\le Q\le 10^5$), z których każdy opisują dwie liczby całkowite $(a,b)$ z $1 \leq a \leq b \leq N$, podające indeksy końców zakresu $a \ldots b$, który ma pozostać niepomalowany.

Dla każdego zakresu kandydata określ minimalną liczbę pociągnięć pędzla potrzebną, by pomalować każdy odcinek poza nim na pożądany kolor, pozostawiając wszystkie odcinki wewnątrz niepomalowane. Bessie nie wykonuje faktycznie żadnego malowania w tym procesie, więc odpowiedzi dla poszczególnych zakresów są niezależne.

Wejście

Pierwszy wiersz zawiera $N$ i $Q$.

Następny wiersz zawiera napis długości $N$ opisujący pożądany kolor każdego odcinka płotu.

Każdy z kolejnych $Q$ wierszy zawiera dwie liczby całkowite $a$ i $b$, oddzielone spacją, opisujące zakres kandydata, który może pozostać niepomalowany.

Wyjście

Dla każdego z $Q$ kandydatów wypisz odpowiedź w nowym wierszu.

Przykład

Wejście 1

8 2
ABBAABCB
3 6
1 4

Wyjście 1

4
3

Uwagi

W tym przykładzie wyłączenie podzakresu odpowiadającego pożądanemu wzorowi $\texttt{BAAB}$ wymaga czterech pociągnięć pędzla do malowania, natomiast wyłączenie $\texttt{ABBA}$ wymaga tylko trzech.

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

Podzadania

• Testy 1–4 spełniają $N,Q\le 100$.
• Testy 5–7 spełniają $N,Q\le 5000$.
• Testy 8–13 nie mają dodatkowych ograniczeń.

Autorzy zadania: Andi Qu i Brian Dean