{"raw_statement":[{"iden":"problem statement","content":"You are given a string $S = S_1S_2\\ldots S_N$ of length $N$ consisting of lowercase English letters.\nAdditionally, you are given $Q$ queries about the string $S$. For $i = 1, 2, \\ldots, Q$, the $i$\\-th query is represented by two integers $l_i, r_i$ and asks the following.\n\n> In the substring $S_{l_i}S_{l_i+1}\\ldots 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 \\leq p \\leq r_i-1$ and $S_p = S_{p+1}$?\n\nPrint the answer for each of the $Q$ queries."},{"iden":"constraints","content":"*   $N$ and $Q$ are integers.\n*   $1 \\leq N, Q \\leq 3 \\times 10^5$\n*   $S$ is a string of length $N$ consisting of lowercase English letters.\n*   $l_i$ and $r_i$ are integers.\n*   $1 \\leq l_i \\leq r_i \\leq N$"},{"iden":"input","content":"The input is given from Standard Input in the following format:\n\n$N$ $Q$\n$S$\n$l_1$ $r_1$\n$l_2$ $r_2$\n$\\vdots$\n$l_Q$ $r_Q$"},{"iden":"sample input 1","content":"11 4\nmississippi\n3 9\n4 10\n4 6\n7 7"},{"iden":"sample output 1","content":"2\n2\n0\n0\n\nThe answers to the four queries are as follows.\n\n*   For the first query, $S_3S_4\\ldots S_9 = $ `ssissip` has two places where the same lowercase English letter occurs twice in a row: $S_3S_4 = $ `ss` and $S_6S_7 = $ `ss`.\n*   For the second query, $S_4S_5\\ldots S_{10} = $ `sissipp` has two places where the same lowercase English letter occurs twice in a row: $S_6S_7 = $ `ss` and $S_9S_{10} = $ `pp`.\n*   For the third query, $S_4S_5S_6 = $ `sis` has zero places where the same lowercase English letter occurs twice in a row.\n*   For the fourth query, $S_7 = $ `s` has zero places where the same lowercase English letter occurs twice in a row."},{"iden":"sample input 2","content":"5 1\naaaaa\n1 5"},{"iden":"sample output 2","content":"4\n\n$S_1S_2\\ldots S_5 = $ `aaaaa` has four places where the same lowercase English letter occurs twice in a row: $S_1S_2 = $ `aa`, $S_2S_3 = $ `aa`, $S_3S_4 = $ `aa`, and $S_4S_5 = $ `aa`."}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}