#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>
#include <cmath>
#include <cctype>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <vector>
#include <stack>
#include <ctime>
#include <cstdlib>
#include <cstdlib>
#include <cstring>
#include <string.h>
#include <cstdio>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef vector<int> VI;
typedef vector<ll> VL;

#define sp system("pause")
#define pn printf("\n");
typedef pair<int, int> pii;
#define se(a) a.begin(),a.end()

const int MAXN = 1e6;

int num[26][MAXN];
char str[MAXN];

int main()
{
    int T;
    cin >> T;
    int cas = 1;
    while (T--)
    {
        int n, q;
        scanf("%d%d", &n, &q);
        scanf("%s", str+1);
        int len = strlen(str+1);
        for (int i = 0; i <= len; i++)for (int j = 0; j < 26; j++)num[j][i] = 0;
        for (int i = 1; i <= len; i++)
        {
            for (int j = 0; j < 26; j++)
            {
                num[j][i] = num[j][i - 1];
            }
            num[str[i] - 'A'][i]++;
        }
        printf("Case #%d:\n", cas++);
        while (q--)
        {
            int l, r;
            scanf("%d%d", &l, &r);
            int ans = -1;
            for (int i = 0; i < 26; i++)
            {
                if (num[i][r] - num[i][l - 1] != 0)
                {
                    ans = num[i][r] - num[i][l - 1];
                    break;
                }
            }
            printf("%d\n", ans);
        }
    }
}