Немає часу малювати
Бесі нещодавно отримала набір фарб і хоче розмалювати довгу огорожу з одного боку свого пасовища. Огорожа складається з n послідовних 1-метрових сегментів. У Бесі є фарби 26 різних кольорів, які вона позначила літерами від 'A' до 'Z' у порядку зростання темряви ('A' - найсвітліший колір, 'Z' - найтемніший). Таким чином, вона може описати розфарбування огорожі як рядок з n символів (де кожен символ - це одна з літер від 'A' до 'Z').
Спочатку всі сегменти огорожі не розфарбовані. Бесі може розфарбувати будь-який неперервний діапазон сегментів одним кольором за одне доторкання пензля, причому вона ніколи не фарбує світлішим поверх темнішого (вона може фарбувати темнішим поверх світлішого).
Наприклад, спочатку не пофарбований відрізок довжини 4 вона може пофарбувати так:
.... -> BBB. -> BBLL -> BQQL
Обмежена в часі, Бесі може залишити деякі послідовні відрізки не пофарбованими. Зараз вона розглядає q кандидатів відрізків, кожен задається двома цілими числами (a, b) (1 ≤ a ≤ b ≤ n), що вказують індекси кінцевих точок відрізка, які повинні залишитися не пофарбованими.
Для кожного кандидата вкажіть мінімальну кількість доторкань, яке потрібно, щоб пофарбувати всі сегменти поза цим діапазоном у бажаний колір, залишаючи сегменти всередині діапазону не пофарбованими. Зазначимо, що Бесі насправді нічого не фарбує, тому відповіді для кожного діапазону-кандидата незалежні.
Вхідні дані
Перша рядок містить n (1 ≤ n ≤ 10^5) і q (1 ≤ q ≤ 10^5).
Наступний рядок містить рядок довжини n, що представляє бажаний колір кожного сегмента огорожі.
Кожен з наступних q рядків містить два цілі числа a і b, які представляють діапазон сегментів, що можливо залишаться не пофарбованими.
Вихідні дані
Для кожного з q кандидатів виведіть відповідь на новому рядку.
Приклад
У цьому прикладі, виключення діапазону відповідає бажаному зразку. У цьому прикладі виключення діапазону BAAB вимагає чотири доторкання для фарбування, а виключення діапазону ABBA - лише три.
.... -> AA.. -> ABBB -> ABCB