题目描述

给出一个长度为$n$且只包含大写英文字母的字符串$S$，然后有$Q$个询问，每次给出一个区间，然后询问这个区间中有多少个 AC

输入描述

第一行输入两个正整数$n,Q(1\le n,Q\le 10^5)$， 含义如题所示

第二行输入一个长度为$n$且只包含大写英文字母的字符串$S$

接下来$Q$行，每行给出两个正整数$l_i,r_i(1\le l_i\le r_i\le n)$

输出描述

输出一共$Q$行，第$i$行输出一个整数代表第$i$个询问的答案

样例

输入

8 3
ACACTACG
3 7
2 3
1 8

输出

2
0
3