Consecutive

You are given a string $s=s_1{s}_2...s_n$ of length $n$ consisting of lowercase English letters.

Additionally, you are given $q$ queries about the string $s$. For $i=1,2,...,q$, the $i$-th query is represented by two integers $l_i,r_i$ and asks the following:

• In the substring $s_{l_i}{s}_{l_{i+1}}...s_{r_i}$ of $s$, which ranges from the $l_i$-th to the $r_i$-th character, how many places are there where the same lowercase English letter occurs twice in a row? In other words, how many integers $p$ satisfy $l_i\le p\le r_i-1$ and $s_p=s_{p+1}$?

Print the answer for each of the $q$ queries.

Input

The first line contains two integers $n$ and $q(1\le n,q\le 3\cdot 10^5)$.

The second line is a string $s$ of length $n$ consisting of lowercase English letters.

Each of the next $q$ lines contains a query $(l_i,r_i),1\le l_i,r_i\le n,1\le i\le q$.

Output

Print $q$ lines. For $i=1,2,...,q$, the $i$-th line should contain the answer to the $i$-th query.

Examples