#include <fstream>
#define Xp 602
using namespace std;
ifstream f("perb.in");
ofstream g("perb.out");
int i,j,l,x,y,cnt,sum,n,m,dp[Xp][Xp],fr[4][Xp],Cod[Xp],luff[Xp];
char s[Xp];
int maxi(int a,int b)
{
    return a>b?a:b;
}
int mini(int a,int b)
{
    return a>b?b:a;
}
int main()
{

    f>>n>>m>>(s+1);
    for(i=1;i<=n;++i)
        for(j=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[s[l]-'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[cnt][Cod[l]]++;
                if(l>j) fr[cnt][Cod[l-j]]--;
                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--)
    {
        f>>x>>y;
        g<<dp[x][y]<<'\n';
    }
    return 0;
}