#include #include #include #include #include #include #include #include #include #include using namespace std; const int inf=(1<<30)-1; const int maxn=100010; #define REP(i,n) for(int i=(0);i<(n);i++) #define FOR(i,j,n) for(int i=(j);i<=(n);i++) #define Rep(x) for(int i=head[x],y;~i;i=e[i].next) if(!vis[y=e[i].to]) typedef long long ll; typedef pair PII; int IN(){ int c,f,x; while (!isdigit(c=getchar())&&c!='-');c=='-'?(f=1,x=0):(f=0,x=c-'0'); while (isdigit(c=getchar())) x=(x<<1)+(x<<3)+c-'0';return !f?x:-x; } #define de(x) cout << #x << "=" << x << endl #define MP make_pair #define PB push_back #define fi first #define se second int n,q,T; char s[maxn]; int S[30][maxn]; int main() { int T;scanf("%d",&T); int cnt=0; while(T--) { scanf("%d%d",&n,&q); scanf("%s",s+1); memset(S,0,sizeof(S)); for(int i=1;i<=n;i++) { for(int j=0;j<26;j++) S[j][i]=S[j][i-1]+(s[i]-'A'==j?1:0); } printf("Case #%d:\n",++cnt); while(q--) { int l,r;scanf("%d%d",&l,&r); int ans=0,flag=0; for(int i=0;i<26&&!flag;i++) { if(S[i][r]-S[i][l-1]>0) ans=S[i][r]-S[i][l-1],flag=1; } printf("%d\n",ans); } } return 0; }