#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<cmath>
#include<algorithm>
#include<map>
#include<vector>
#include<queue>
#include<set>
#define LL long long 
using namespace std;
const int MaxN = 1e5;
const int Inf = 1 << 30;

char s[MaxN + 5];
int sum[30][MaxN + 5];

int main(){
    int T,n,m,l,r;
    for(int i = 1;i <= 26;i++) sum[i][0] = 0;
    while(~scanf("%d",&T)){
        for(int cas = 1;cas <= T;cas++){
            printf("Case #%d:\n",cas);
            scanf("%d %d",&n,&m);
            scanf("%s",s + 1);
            for(int i = 1;i <= n;i++){
                for(int j = 1;j <= 26;j++){
                    sum[j][i] = sum[j][i - 1];
                    if(s[i] - 'A' + 1 == j) sum[j][i]++;
                }
            }
            for(int i = 1;i <= m;i++){
                scanf("%d %d",&l,&r);
                for(int j = 1;j <= 26;j++){
                    if(sum[j][r] - sum[j][l - 1] > 0){
                        printf("%d\n",sum[j][r] - sum[j][l - 1]);
                        break;
                    }
                }
            }
        }
    }
    return 0;
}