#include <stdio.h>

int a[310],c[310],g[310],t[310],q[310],sol[610][610],n,m,nd,d[100];
char v[620];

inline int max(int x,int y,int z,int u)
{
    int aux=x;
    if (y>aux) aux=y;
    if (z>aux) aux=z;
    if (u>aux) aux=u;
    return aux;
}

int main()
{
    int x,y,aux,i,j,k,s;
    freopen("perb.in","r",stdin);
    freopen("perb.out","w",stdout);
    scanf("%d %d\n",&n,&m);
    v[0]=' ';
    fgets(v+1,605,stdin);
    for (i=1;i<=n;++i)
        for (j=1;j<=n;++j)
            sol[i][j]=1000;
    for (i=1;i<=n;++i)
        sol[i][i]=0;
    for (i=2;i<=n;++i)
    {
        nd=0;x=i;
        for (j=2;j*j<i;++j)
            if (x%j==0)
            {
                ++nd;
                d[nd]=i/j;
                while (x%j==0) x/=j;
            }
        if (x!=1) {++nd;d[nd]=i/x;}
        for (j=1;j<=nd;++j)
        {
            for (k=0;k<d[j];++k)
            {
                a[k]=0;
                c[k]=0;
                g[k]=0;
                t[k]=0;
            }
            for (k=1;k<=i;++k)
            {
                if (v[k]=='A') ++a[k%d[j]];
                else if (v[k]=='C') ++c[k%d[j]];
                else if (v[k]=='G') ++g[k%d[j]];
                else ++t[k%d[j]];
            }
            s=0;
            for (k=0;k<d[j];++k)
            {
                q[k]=max(a[k],c[k],g[k],t[k]);
                s=a[k]+c[k]+g[k]+t[k]-q[k];
            }
            if (s<sol[1][i]) sol[1][i]=s;
            for (k=2;k<=n-i+1;++k)
            {
                aux=(k-1)%d[j];
                s-=a[aux]+c[aux]+g[aux]+t[aux]-q[aux];
                if (v[k-1]=='A') --a[aux];
                else if (v[k-1]=='C') --c[aux];
                else if (v[k-1]=='G') --g[aux];
                else --t[aux];
                if (v[k+i-1]=='A') ++a[aux];
                else if (v[k+i-1]=='C') ++c[aux];
                else if (v[k+i-1]=='G') ++g[aux];
                else ++t[aux];
                q[aux]=max(a[aux],c[aux],g[aux],t[aux]);
                s+=a[aux]+c[aux]+g[aux]+t[aux]-q[aux];
                if (s<sol[k][k+i-1]) sol[k][k+i-1]=s;
            }
        }
    }
    for (i=1;i<=m;++i)
    {
        scanf("%d%d",&x,&y);
        if (x>y)
        {
            aux=x;
            x=y;
            y=aux;
        }
        printf("%d\n",sol[x][y]);
    }
    return 0;
}