#include <iostream>
#include<stdio.h>
using namespace std;
int r[26][100001];
char s[100001];
int main()
{
//    int **r=new int*[26];

    int T;
    cin>>T;
    for(int i=0;i<T;i++){
        cout<<"Case #"<<i+1<<':'<<endl;
        int a,b;
        scanf("%d%d",&a,&b);
         /*for(int i=0;i<26;i++){
        r[i]=new int[a];
    }*/
      //  string s;
        cin>>s;
        //scanf("%s",s);
        for (int i=0;i<a;i++)
        for(int j=0;j<26;j++){
            r[j][i+1]=r[j][i]+(s[i]-'A'==j);
        }
        for(int z=0;z<b;z++){
            int x,y;
            scanf("%d%d",&x,&y);
            //cin>>x>>y;
            //cout<<endl<<c<<endl;
            for(int j=0;j<26;j++)
                if(r[j][y]-r[j][x-1]){
                
                cout<<r[j][y]-r[j][x-1]<<endl;
                break;
                }
        }

    }
    return 0;
}