output_description: Print Q lines. The i-th line should contain the answer to the i-th query.
  
  * * *
input_description: Input is given from Standard Input in the following format:
  
      
      
      N Q
      S
      l_1 r_1
      :
      l_Q r_Q
attempt: # データ構造：ヒープ
  import heapq
  
  
  class heapque:
      def __init__(self, *args):
          self.que = []
          for arg in args:
              self.push(arg)
  
      def push(self, v):
          heapq.heappush(self.que, v)
  
      def pop(self):
          return heapq.heappop(self.que)
  
  
  # 定数
  INF = float("inf")
  MOD = int(1e9 + 7)
  
  
  def int1(n):
      return int(n) - 1
  
  
  # エントリーポイント
  def main():
      N, Q = map(int, input().split())
      S = input()
      LR = tuple(map(int1, input().split()) for _ in range(Q))
  
      add_sum = [0]
      for n in range(1, N):
          add_sum += [add_sum[-1] + (S[n - 1 : n + 1] == "AC")]
      print(add_sum)
  
      for l, r in LR:
          print(add_sum[r] - add_sum[l])
  
  
  main()
  
problem_description: Statement
  
  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?
samples: [{"input": "8 3\n    ACACTACG\n    3 7\n    2 3\n    1 8", "output": "2\n    0\n    3\n    \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."}]