#include<cstdio>
#include<cctype>
#include<algorithm>
using std::sort;
int v[605];
int solve(int v[],int n){
    int ans=600;
    for(int p=n-1;p;p--){
        if(n%p)continue;
        int nr=0;
        for(int i=0;i<p;i++){
            int vv[605],nn=n/p;
            for(int j=0;j<nn;j++)
                vv[j]=v[p*j+i];
            sort(vv,vv+nn);
            int cnr=1,mnr=1,emaj=vv[0];
            for(int i=1;i<nn;i++)
                if(vv[i]==vv[i-1])
                    cnr++;
                else if(cnr>mnr)
                    mnr=cnr,emaj=vv[i-1];
            for(int j=0;j<nn;j++)
                if(vv[j]!=emaj)nr++;
        }
        ans=nr<ans?nr:ans;
    }
    return ans;
}
int main(){
    freopen("perb.in","r",stdin);
    freopen("perb.out","w",stdout);
    int n,m,x,y;
    scanf("%d %d",&n,&m);
    char c;
    while(!isalpha(c=getchar()));ungetc(c,stdin);
    for(int i=0;i<n;i++)
        if((c=getchar())=='A')v[i]=0;
        else if(c=='C')v[i]=1;
        else if(c=='G')v[i]=2;
        else if(c=='T')v[i]=3;
    for(int i=0;i<m;i++){
        scanf("%d%d",&x,&y);x--;
        printf("%d\n",solve(v+x,y-x));
    }
    return 0;
}