#include<bits/stdc++.h>
using namespace std;

#define INF 0x3f3f3f3f
const int maxn=1e5+100;
const double eps=1e-10;
const long long mod=1e9+7;

typedef long long ll;
typedef unsigned long long ull;

int T,Case;
int dp[maxn][30];
int n,q,l,r;
string s;   
int main() {
    #ifdef ac
        freopen("in.txt","r",stdin);
        freopen("out.txt","w",stdout);
    #endif
    ios::sync_with_stdio(0); cin.tie(0);
    for(cin >> T;T;T--) {
        cin >> n >> q >> s;
        for(int i=0;i<n;++i) {
            for(int j=0;j<26;++j) {
                dp[i+1][j]=dp[i][j];
            }
            dp[i+1][s[i]-'A']++;
        }
        cout << "Case #" << ++Case << ":" << endl;
        while(q--){
            cin >> l >> r;
            for(int i=0;i<26;++i) {
                if(dp[r][i]-dp[l-1][i]) {
                    cout << dp[r][i]-dp[l-1][i] << endl;
                    break;
                }
            }
        }
    }
    return 0;
}