#include <cstdio>
#include <algorithm>

using namespace std;
const int maxn = 1e5+9;
int T,n,q;
//int a[maxn];
int sum[26][maxn];
int val[20][maxn];

void init()
{
    char temp;
    scanf("%d %d\n",&n,&q);
    for( int i = 0; i < 26; i++ ) sum[i][0] = 0;
    for( int i = 1; i <= n; i++ )
    {
        temp = getchar();
        val[0][i] = temp-'A'; //[0-25]
        for( int j = 0; j < 26; j++ ) sum[j][i] = sum[j][i-1];
        sum[val[0][i]][i]++;
    }
    for( int k = 1 , l = 2; l <= n; k++ , l<<=1 )
        for( int i = 1; i + l - 1 <= n; i++ )
        {
            int mid = i + l/2;
            val[k][i] = min( val[k-1][i] , val[k-1][mid] );
        }
}
int query( int l , int r )
{
    int index = 0 , len = 1;
    while( ( len<<1 ) <= r-l+1 ) index++ , len<<=1;
    return min( val[index][l] , val[index][r-len+1] );
}
void solve()
{
    int l , r;
    for( int i = 1; i <= q; i++ )
    {
        scanf("%d%d",&l,&r);
        int k = query(l,r);
        printf("%d\n",sum[k][r]-sum[k][l-1]);
    }
}
int main()
{
    scanf("%d",&T);
    for( int kase = 1; kase <= T; kase++ )
    {
        init();
        printf("Case #%d:\n",kase);
        solve();
    }
    return 0;
}