#include<bits/stdc++.h>
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define int ll
using namespace std;
typedef long long ll;
#define Rep(i,a,b) for(register int i=(a);i<=int(b);++i)
#define Dep(i,a,b) for(register int i=(a);i>=int(b);--i)
#define rep(i,a,b) for(register int i=(a);i<int(b);++i)
#define mem(x,v) memset(x,v,sizeof(x))
#define gc getchar
#define pc putchar
#define fi first
#define se second
#define debug(x) cout << #x" = " << x << endl;
#define pp(x,y) cout << "pp: " << x << " " << y << endl;
#define rank __RANK
inline ll read(){
    register ll x=0,f=1;register char c=gc();
    for(;!isdigit(c);c=gc())if(c=='-')f=-1;
    for(;isdigit(c);c=gc())x=(x<<1)+(x<<3)+(c^48);
    return x*f;
}
#define rd read
void write(ll x){if(x<0)x=-x,pc('-');if(x>=10)write(x/10);putchar(x%10+'0');}
void writeln(ll x){write(x);puts("");}
const int maxn = 1e5+233;
int T,n,q;
int a[maxn],sum[maxn][26];
signed main(){
    int T = rd();
    for(int Case=1;Case<=T;++Case){
        printf("Case #%d:\n",Case);
        n = rd(),q = rd();
        Rep(i,1,n){
            a[i] = gc();
            if(a[i] < 'A' || a[i] > 'Z') a[i] = gc();
            rep(j,0,26){
                sum[i][j] = sum[i-1][j] + ((a[i]-'A') == j);
            }
        }
        while(q--){
            int l = rd(),r = rd();
            rep(i,0,26){
                if(sum[r][i] - sum[l-1][i] != 0){
                    writeln(sum[r][i] - sum[l-1][i]);
                    break;
                }
            }
        }
    }
    return 0;
}