#include<stdio.h>
#include<math.h>
char sir[669];
int x[669];

int solve(int div,int x0,int x1)
{
    int f[5]; f[1]=f[2]=f[3]=f[4]=0;
    int i,j,s=0,max;
    for(i=x0;i<=x0+div-1;i++)
        {
            f[1]=f[2]=f[3]=f[4]=0;
            for(j=i;j<=x1;j+=div)
                f[x[j]]++;
            max=f[1];
            if(f[2]>max)
                max=f[2];
            if(f[3]>max)
                max=f[3];
            if(f[4]>max)
                max=f[4];
            s+=f[1]+f[2]+f[3]+f[4]-max;
        }
   return s;
}

int main()
{
    int n,m,i,x0,x1,N,lim,val=0,max=0,d;
    
    freopen("perb.in","r",stdin);
    freopen("perb.out","w",stdout);

    scanf("%d%d\n",&n,&m);
    gets(sir+1);
    for(i=1;i<=n;i++)
    {
        if(sir[i]=='A')
            x[i]=1;
        if(sir[i]=='C')
            x[i]=2;
        if(sir[i]=='G')
            x[i]=3;
        if(sir[i]=='T')
            x[i]=4;
    }
    for(i=1;i<=m;i++)
    {
        max=-1;
        scanf("%d%d",&x0,&x1);
        N=x1-x0+1;
        lim=sqrt(N);
        for(d=1;d<=lim;d++)
            if(N%d==0)
                {
                    val=solve(d,x0,x1);
                    if(val<max || max==-1)
                           max=val;
                    if(d*d!=N && d!=1)
                    {
                        val=solve(N/d,x0,x1);
                        if(val<max || max==-1)
                            max=val;
                    }

                }
        printf("%d\n",max);
    }
    return 0;
}