You are given a string $S$ of length $N$ consisting of `A`, `C`, `G` and `T`. Answer the following $Q$ queries:

-   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?

Notes
A substring of a string $T$ is a string obtained by removing zero or more characters from the beginning and the end of $T$.

For example, the substrings of `ATCODER` include `TCO`, `AT`, `CODER`, `ATCODER` and (the empty string), but not `AC`.

Input is given from Standard Input in the following format:

```
$N$ $Q$
$S$
$l_1$ $r_1$
$:$
$l_Q$ $r_Q$
```

Print $Q$ lines. The $i$-th line should contain the answer to the $i$-th query.

-   $2 \leq N \leq 10^5$
-   $1 \leq Q \leq 10^5$
-   $S$ is a string of length $N$.
-   Each character in $S$ is `A`, `C`, `G` or `T`.
-   $1 \leq l_i &lt; r_i \leq N$

2
0
3

• 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.
• 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.
• 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.