#include <cstdio>
#include <cctype>
#define MAXN 600
#define BUF_SIZE 4096
char buf[BUF_SIZE];
int pos=BUF_SIZE, s[MAXN+1][4], max[MAXN+1], d[MAXN+1][MAXN+1], a[MAXN+1];
FILE *fin;
inline char nextch(){
    if(pos==BUF_SIZE){
        fread(buf, BUF_SIZE, 1, fin);
        pos=0;
    }
    return buf[pos++];
}
inline int read(){
    int x=0;
    char ch=nextch();
    while(!isdigit(ch)){
        ch=nextch();
    }
    while(isdigit(ch)){
        x=10*x+ch-'0';
        ch=nextch();
    }
    return x;
}
int main(){
    int n, q, i, j, p, t, x, y, lim, f[256], r, c;
    FILE *fout;
    fin=fopen("perb.in", "r");
    fout=fopen("perb.out", "w");
    fscanf(fin, "%d%d ", &n, &q);
    f['T']=0;
    f['A']=1;
    f['G']=2;
    f['C']=3;
    for(i=1; i<=n; i++){
        a[i]=f[(int)nextch()];
    }
    for(i=1; i<=n; i++){
        for(j=i; j<=n; j++){
            d[i][j]=j-i;
        }
    }
    for(i=1; i<=n; i++){
        lim=(n-i+1)/2;
        for(j=1; j<=lim; j++){
            for(p=i, r=0; r<j; p++, r++){
                s[r][0]=s[r][1]=s[r][2]=s[r][3]=0;
                s[r][a[p]]=max[r]=1;
            }
            for(t=1; i+j*(t+1)<=n+1; t++){
                c=0;
                for(p=i+t*j, r=0; r<j; p++, r++){
                    s[r][a[p]]++;
                    if(s[r][a[p]]>max[r]){
                        max[r]=s[r][a[p]];
                    }
                    c+=t+1-max[r];
                }
                if(d[i][i+j*(t+1)-1]>c){
                    d[i][i+j*(t+1)-1]=c;
                }
            }
        }
    }
    for(; q; q--){
        x=read();
        y=read();
        fprintf(fout, "%d\n", d[x][y]);
    }
    fclose(fin);
    fclose(fout);
    return 0;
}