#include <fstream>
#include <string.h>

#define inf 10000
using namespace std;
ifstream fin("perb.in");
ofstream fout("perb.out");
int i,j,n,m,k,l,sum,v[603],D[603][603],x,y,d,ap[603][4],c,nrmax;
char ch;
int val(char x)
{
    if(x=='A')
        return 0;
    if(x=='C')
        return 1;
    if(x=='G')
        return 2;
    return 3;
}
int main()
{
    fin>>n>>m;
    for(i=1;i<=n;i++)
    {
        fin>>ch;
        v[i]=val(ch);
    }
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
            if(i!=j)
                D[i][j]=inf;
    for(d=1;d<=n;d++)
    {
        for(i=1;i<=n;i++)
        {
            memset(ap,0,sizeof(ap));
            for(j=i;j<=n;j++)
            {
                ap[(j-i+1)%d][v[j]]++;
                if((j-i+1)%d==0&&(j-i+1)/d>1)
                {
                    c=0;
                    for(k=0;k<d;k++)
                    {
                        nrmax=0;
                        for(l=0;l<=3;l++)
                        {
                            nrmax=max(nrmax,ap[k][l]);
                        }
                        c+=(j-i+1)/d-nrmax;
                    }
                    D[i][j]=min(D[i][j],c);
                }
            }
        }
    }
    for(i=1;i<=m;i++)
    {
        fin>>x>>y;
        fout<<D[x][y]<<'\n';
    }
    return 0;
}