#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
#define lson rt<<1
#define rson rt<<1|1

char s[100010];
int sum[100010][26],a[100010],Min[400010];

void Build( int l , int r , int rt )
{
    if ( l==r )
    {
        Min[rt] = a[l];
        return;
    }
    int mid = ( l+r )>>1;
    Build ( l , mid , lson );
    Build ( mid+1 , r , rson );
    Min[rt] = min ( Min[lson] , Min[rson] );
}

int Query( int L , int R , int l , int r , int rt )
{
    if ( L<=l&&R>=r )
        return Min[rt];
    int mid = ( l+r )>>1,ans = 33;
    if ( L<=mid )
        ans = min ( ans , Query( L , R , l , mid , lson ) );
    if ( R>mid )
        ans = min ( ans , Query( L , R , mid+1 , r , rson ) );
    return ans;
}

int main()
{
    for ( int T ; scanf ( "%d" , &T )==1 ; )
    {
        for ( int cas=1 ; cas<=T ; cas++ )
        {
            int n,q;
            char c;
            scanf ( "%d%d" , &n , &q );
            scanf ( "%s" , s );
            for ( int i=0 ; i<26 ; i++ )
                sum[0][i] = 0;
            for ( int i=1 ; i<=n ; i++ )
               a[i] = s[i-1]-'A';
            for ( int i=1 ; i<=n ; i++ )
            {
                for ( int j=0 ; j<26 ; j++ )
                    sum[i][j] = sum[i-1][j];
                sum[i][a[i]]++;
            }
            Build ( 1 , n , 1 );
            printf ( "Case #%d:\n" , cas );
            for ( int i=1 ; i<=q ; i++ )
            {
                int l,r; scanf ( "%d%d" , &l , &r );
                int t = Query( l , r , 1 , n , 1 );
                printf ( "%d\n" , sum[r][t]-sum[l-1][t] );
            }
        }
    }
    return 0;
}