#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<string>
#include<functional>            
#include<fstream>
#include<ctime>
#include<bitset>
#include<sstream>
#include<cassert>
using namespace std;

#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(),(x).end()
#define INS(x) inserter(x,x.begin())
#define pb push_back
#define mp make_pair
#define rep(i,l,r) for (int i=l;i<r;i++)
#define per(i,l,r) for (int i=r-1;i>=l;i--)
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> point;
typedef pair<int, int> pii;
const ll inf = 9.2e18;
const int maxn = 1e5 + 70;
const int INF = 2.1e9;
const int maxm = 1e6 + 70;
const int MOD = 1e9 + 7;
const double eps = 1e-7;
const double PI = acos(-1.0);

int n, m, k, Q;

char s[maxn];

int vis[maxn][26];

int main(){
    //freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
    int T;
    cin >> T;
    for (int kase = 1; kase <= T; kase++){
        memset(vis, 0, sizeof(vis));
        cin >> n >> Q;
        scanf("%s", s);
        for (int i = 0; i < n; i++){
            for (int j = 0; j < 26; j++) vis[i + 1][j] = vis[i][j];
            vis[i + 1][s[i] - 'A']++;
        }

        cout << "Case #" << kase << ":" << endl;
        while (Q--){
            int l, r;
            scanf("%d%d", &l, &r);
            for (int i = 0; i < 26; i++){
                int x = vis[r][i] - vis[l - 1][i];
                if (x){
                    printf("%d\n", x);
                    break;
                }
            }
        }
    }
    return 0;
}