#include<fstream>
#include<cstring>
#define N 610
using namespace std;
ifstream f("perb.in");
ofstream g("perb.out");
int n,m,i,j,k,l,x,y,sol,cate,nr[N][4],v[N],d[N][N];
char s[N];
inline int ce(char x)
{
    if(x=='A')
    return 0;
    if(x=='C')
    return 1;
    if(x=='G')
    return 2;
    if(x=='T')
    return 3;
}
inline int maxim()
{
    return max(max(nr[l][0],nr[l][1]),max(nr[l][2],nr[l][3]));
}
int main()
{
    f>>n>>m;
    f>>(s+1);
    for(i=1;i<=n;++i)
    v[i]=ce(s[i]);
    for(i=1;i<=n;++i)
    for(j=i+1;j<=n;++j)
    d[i][j]=j-i;
    for(i=1;i<=n;++i)
    for(j=1;i+2*j-1<=n;++j)
    {
        memset(nr,0,sizeof(nr));
        for(l=0;l<j;++l)
        ++nr[l][v[i+l]];
        cate=1;
        for(k=i+j;k+j-1<=n;k+=j)
        {
            sol=0;
            ++cate;
            for(l=0;l<j;++l)
            ++nr[l][v[k+l]],sol+=cate-maxim();
            d[i][k+j-1]=min(d[i][k+j-1],sol);
        }
    }
    for(i=1;i<=m;++i)
    {
        f>>x>>y;
        g<<d[x][y]<<'\n';
    }
    return 0;
}