#include <bits/stdc++.h>
#define X           first
#define Y           second
#define pb          push_back
#define mp          make_pair
#define SZ(X)       (X.size())
#define mst(a,b)    memset((a),(b),sizeof(a))
#define lowbit(a)   ((a)&(-a))
using namespace std;
typedef long long LL;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<LL, LL> pll;
const int N = 5e5 + 10;
const int mod = 1e9+7;
const int inf = 0x3f3f3f3f;
const LL INF = 1LL << 61;
const int maxn=100000+10;
char s[maxn];
int sum[26][maxn];
int main() {
#ifdef local
    freopen("in.txt", "r", stdin);
#endif // local
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int T,cas=1; cin>>T;
    while (T--){
        int n,q; cin>>n>>q;
        cin>>(s+1);
        for (int i=1;i<=n;i++){
            for (int j=0;j<26;j++){
                sum[j][i]=sum[j][i-1]+(s[i]-'A'==j);
            }
        }
        cout<<"Case #"<<cas++<<":\n";
        for (int i=0;i<q;i++){
            int l,r; cin>>l>>r;
            for (int j=0;j<26;j++){
                if (sum[j][r]-sum[j][l-1]){
                    cout<<sum[j][r]-sum[j][l-1]<<"\n";
                    break;
                }
            }
        }
    }
    return 0;
}