/*

*/
#include <bits/stdc++.h>
#define fi first
#define se second
#define lc i << 1
#define rc i << 1 | 1
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
const int inf = 0x3f3f3f3f;

char s[N];
int vis[30][N];

int main()
{
    int T; scanf("%d", &T);
    for(int _ = 1; _ <= T; _ ++)
    {
        printf("Case #%d:\n", _);
        int n, q, l, r;
        memset(vis, 0, sizeof vis);
        scanf("%d%d%s", &n, &q, s + 1);
        for(int i = 1, len = strlen(s + 1); i <= len; i ++)
        {
            for(int j = 0; j < 26; j ++)
            {
                vis[j][i] = vis[j][i-1];
            }
            vis[s[i] - 'A'][i] ++;
        }
        while(q --)
        {
            scanf("%d%d", &l, &r);
            for(int i = 0; i < 26; i ++)
            {
                if(vis[i][r] - vis[i][l-1])
                {
                    printf("%d\n", vis[i][r] - vis[i][l-1]);
                    break;
                }
            }
        }
    }
    return 0;
}