#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn = 100010;
int n, q; char s[maxn];
int a[maxn][27];
int main(){
    int w;  scanf("%d",&w);
    for(int _w = 1; _w <= w; _w++){
        printf("Case #%d:\n", _w);
        scanf("%d%d",&n,&q);
        scanf("%s",s+1);
        int len = strlen(s+1);
        memset(a,0,sizeof(a));
        for(int i = 1; i <= len; i++){
            for(int j = 0; j <= 25; j++)
                a[i][j] = a[i-1][j];
            a[i][s[i]-'A']++;
        }
        for(int i = 1; i <= q; i++){
            int l, r;  scanf("%d%d",&l,&r);
            for(int j = 0; j <= 25; j++){//从小到大枚举
                if(a[r][j]-a[l-1][j] != 0){//存在该字符
                    printf("%d\n",a[r][j]-a[l-1][j]);//输出
                    break;
                }
            }
        }
    }
    return 0;
}