Бесі нещодавно отримала набір фарб, і вона хоче розмалювати довгу огорожу з одного боку її пасовища. Огорожа складається з \(N\) послідовних 1-метрових сегментів (\(1\le N\le 10^5\)). У Бесі є фарби 26 різних кольорів, які вона помітила літерами від 'A' до Z' у порядку зростання темноти ('A' - найбільш світлий колір, 'Z' - найтемніший). Тому вона може описувати розмальовку огорожі як рядок N символів (де кожен символ один з - від 'A' до Z').

Спочатку всі сегменти огорожі не розфарбовані. Бесі може розфарбувати будь-який безперервний діапазон сегментів одним кольором за один дотик пензля, також вона ніколи не фарбує світлішим поверх більш темного (вона може фарбувати більше темним поверх світлішого).

Наприклад, спочатку не пофарбований відрізок довжини 4 вона може пофарбувати так:

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

Обмежена в часі, Бесі може залишити деякі послідовні відрізки не пофарбовані. Зараз вона розглядає \(Q\) відрізків (\(1\le Q\le 10^5\)), кожен задається двома цілими числами \((a,b)\) (\(1 \leq a \leq b \leq N\)), що вказують індекси кінцевих точок відрізка, які мають залишитися не розфарбованими.

Для кожного відрізка вкажіть мінімальну кількість дотиків, які потрібні, щоб розфарбувати всі сегменти поза цим діапазоном з бажаним кольором, залишаючи сегменти всередині діапазону не розфарбованими. Зауважимо, що Бесі насправді нічого не розфарбовує, тому відповіді кожного діапазону-відрізка незалежні.

Формат вхідних даних

Перший рядок містить \(N\) та \(Q\).

Наступний рядок містить рядок довжиною \(N\) символів, що представляють бажаний колір для кожного сегмента огорожі.

Кожен із наступних \(Q\) рядків містить два розділені пробілом цілих числа \(a\) і \(b\) представляють діапазон сегментів, які, можливо, залишаться не розфарбованими.

Формат вихідних даних

Для кожного з \(Q\) відрізків виведіть відповідь на новому рядку.

Приклад вхідних даних

8 2
ABBAABCB
3 6
1 4

Приклад вихідних даних

4
3

У цьому прикладі виняток діапазону відповідає бажаному зразку У цьому прикладі виняток діапазону \(\texttt{BAAB}\) вимагає чотири дотику для розмальовки, а виняток діапазону \(\texttt{ABBA}\) - лише три.

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

ОЦІНЮВАННЯ:

• У тестах 1-4 \(N,Q\le 100\).
• У тестах 5-7 satisfy \(N,Q\le 5000\).
• У тестах 8-13 немає додаткових обмежень.