// Author : WangZhikun
// Date   : 2018.08.04

#include <map>
#include <queue>
#include <ctime>
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;
typedef long long ll;

template<typename T> void read(T &x){
    x = 0;ll f = 1;char ch = getchar();
    while(!isdigit(ch)){if(ch == '-')f*=-1;ch = getchar();}
    while(isdigit(ch)){x = x*10+ch-48;ch = getchar();}x*=f;
}

int s[100010][26],u,v;
char st[100010];
int main(){
    int T;
    cin>>T;
    for(int TT = 1;TT<=T;TT++){
        cout<<"Case #"<<TT<<":"<<endl;
        int n,m;
        read(n);read(m);
        scanf("%s",&st);
        for(int i=0;i<26;i++)s[0][i] = 0;
        for(int i=1;i<=n;i++){
            for(int j=0;j<26;j++)s[i][j] = s[i-1][j];
            s[i][st[i-1]-'A']+=1;
        }
        for(int i=0;i<m;i++){
            read(u);read(v);
            for(int j=0;j<26;j++){
                if(s[v][j]-s[u-1][j]>0){
                    cout<<s[v][j]-s[u-1][j]<<endl;
                    break;
                }
            }
        }
    }
    return 0;
}