#include <cstdio>
#define Xp 602
#define maxl (1<<17)
using namespace std;
int i,j,l,x,y,cnt,sum,n,m,dp[Xp][Xp],fr[4][Xp],Cod[Xp],luff[Xp];
int pos=maxl-1;
char sir[maxl];
void Next ()
{
    if (++pos == maxl)
        fread (sir, 1, maxl, stdin), pos = 0;
}
void Read (int &kk)
{
    for (;sir[pos] < '0' || sir[pos] > '9'; Next ()) ;
    for (kk = 0; sir[pos] >= '0' && sir[pos] <= '9'; Next ()) kk = kk * 10 + sir[pos] - '0';
}
char character()
{
    while(sir[pos]<'A'||sir[pos]>'Z') Next();
    char sol=sir[pos];
    Next();
    return sol;
}
int maxi(int a,int b)
{
    return (a>b)?a:b;
}
int mini(int a,int b)
{
    return (a>b)?b:a;
}
int main()
{
    freopen("perb.in","r",stdin);
    freopen("perb.out","w",stdout);
    Read(n);
    Read(m);
    for(i=1;i<=n;++i)
        for(j=i+1;j<=n;++j) dp[i][j]=j-i;
    luff['A'-'A']=1;
    luff['C'-'A']=2;
    luff['G'-'A']=3;
    for(l=1;l<=n;++l) Cod[l]=luff[character()-'A'];
    for(i=1;i<=n;++i)
        for(j=i*2;j<=n;j+=i)
        {
            for(l=sum=cnt=0;l<i;l++) fr[1][l]=fr[2][l]=fr[3][l]=fr[0][l]=0;
            for(l=1;l<=n;++l)
            {
                cnt++;
                if(cnt>=i) cnt-=i;
                sum-=maxi(fr[1][cnt],maxi(fr[2][cnt],maxi(fr[3][cnt],fr[0][cnt])));
                fr[Cod[l]][cnt]++;
                if(l>j) fr[Cod[l-j]][cnt]--;
                sum+=maxi(fr[1][cnt],maxi(fr[2][cnt],maxi(fr[3][cnt],fr[0][cnt])));
                if(l>=j) dp[l-j+1][l]=mini(dp[l-j+1][l],j-sum);
            }
        }
    while(m--)
    {
        Read(x);
        Read(y);
        printf("%ld\n",dp[x][y]);
    }
    return 0;
}