Послідовні

Вам дано рядок $s=s_1{s}_2...s_n$ довжини $n$, що складається з малих літер англійського алфавіту.

Також вам надано $q$ запитів до рядка $s$. Для кожного запиту $i=1,2,...,q$, $i$-й запит задається двома цілими числами $l_i$ та $r_i$ і формулюється наступним чином:

• У підрядку $s_{l_i}{s}_{l_{i+1}}...s_{r_i}$ рядка $s$, який охоплює символи з $l_i$-го по $r_i$-й, скільки є позицій, де одна і та ж мала літера англійського алфавіту зустрічається двічі поспіль? Іншими словами, скільки існує цілих чисел $p$, таких що $l_i\le p\le r_i-1$ і $s_p=s_{p+1}$?

Виведіть відповідь для кожного з $q$ запитів.

Вхідні дані

Перша строка містить два цілі числа $n$ та $q(1\le n,q\le 3\cdot 10^5)$.

Друга строка — це рядок $s$ довжини $n$, що складається з малих літер англійського алфавіту.

Кожна з наступних $q$ строк містить запит $(l_i,r_i),1\le l_i,r_i\le n,1\le i\le q$.

Вихідні дані

Виведіть $q$ рядків. Для кожного $i=1,2,...,q$, $i$-й рядок повинен містити відповідь на $i$-й запит.

Приклади