#include<bits/stdc++.h>
#define clr(x) memset(x,0,sizeof(x))
#define clr_1(x) memset(x,-1,sizeof(x))
#define INF 0x3f3f3f3f
#define LL long long
#define pb push_back
#define ls(i) (i<<1)
#define rs(i) (i<<1|1)
#define mp make_pair
#define fi first
#define se second
#define mod 1000000007
using namespace std;
const int N=1e5+100;
char s[N];
int pre[N][26];
int n,m,k,T;
int l,r;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>T;
    for(int kase=1;kase<=T;kase++)
    {
        cout<<"Case #"<<kase<<":"<<endl;
        cin>>n>>m;
        cin>>s+1;
        for(int i=0;i<26;i++)
            pre[0][i]=0;
        for(int i=1;s[i];i++)
        {
            for(int j=0;j<26;j++)
                if(s[i]-'A'==j)
                    pre[i][j]=pre[i-1][j]+1;
                else
                    pre[i][j]=pre[i-1][j];
        }
        for(int i=1;i<=m;i++)
        {
            cin>>l>>r;
            for(int j=0;j<26;j++)
                if(pre[r][j]-pre[l-1][j]>0)
                {
                    cout<<pre[r][j]-pre[l-1][j]<<endl;
                    break;
                }
        }
    }
    return 0;
}