{"raw_statement":[{"iden":"problem statement","content":"You are given a string $S$ of length $N$ consisting of `A`, `C`, `G` and `T`. Answer the following $Q$ queries:\n\n*   Query $i$ ($1 \\leq i \\leq Q$): You will be given integers $l_i$ and $r_i$ ($1 \\leq l_i < r_i \\leq N$). Consider the substring of $S$ starting at index $l_i$ and ending at index $r_i$ (both inclusive). In this string, how many times does `AC` occurs as a substring?"},{"iden":"notes","content":"A substring of a string $T$ is a string obtained by removing zero or more characters from the beginning and the end of $T$.\nFor example, the substrings of `ATCODER` include `TCO`, `AT`, `CODER`, `ATCODER` and (the empty string), but not `AC`."},{"iden":"constraints","content":"*   $2 \\leq N \\leq 10^5$\n*   $1 \\leq Q \\leq 10^5$\n*   $S$ is a string of length $N$.\n*   Each character in $S$ is `A`, `C`, `G` or `T`.\n*   $1 \\leq l_i < r_i \\leq N$"},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$N$ $Q$\n$S$\n$l_1$ $r_1$\n$:$\n$l_Q$ $r_Q$"},{"iden":"sample input 1","content":"8 3\nACACTACG\n3 7\n2 3\n1 8"},{"iden":"sample output 1","content":"2\n0\n3\n\n*   Query $1$: the substring of $S$ starting at index $3$ and ending at index $7$ is `ACTAC`. In this string, `AC` occurs twice as a substring.\n*   Query $2$: the substring of $S$ starting at index $2$ and ending at index $3$ is `CA`. In this string, `AC` occurs zero times as a substring.\n*   Query $3$: the substring of $S$ starting at index $1$ and ending at index $8$ is `ACACTACG`. In this string, `AC` occurs three times as a substring."}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}