#include <fstream>

#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;
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(l=1;l<=n/2;l++)
    {
        for(i=2*l;i<=n;i+=l)
        {
            for(k=0;k<=3;k++)
            {
                sum=0;
                for(j=i;j>=1;j-=l)
                {
                    sum+=(v[j]!=k);
                    d[j][i]=min(d[j][i]+sum,d[j][i]);
                }
            }
        }
    }
    for(i=1;i<=m;i++)
    {
        fin>>x>>y;
        fout<<d[x][y]<<'\n';
    }
    return 0;
}