#include<fstream>
#include<cstring>
using namespace std;
ifstream f("perb.in"); ofstream g("perb.out");
int nrper,k,i,j,pas,INF,n,Q,sir[603],dp[603][603],a[603][603],ap[603][5];
char s[603];
int maxim(int a, int b) {if(a<b) return b; return a;}
int main()
{   f>>n>>Q>>(s+1);
    for(i=1;i<=n;i++)
        if(s[i]=='A') sir[i]=0;
        else    if(s[i]=='T') sir[i]=1;
                else    if(s[i]=='C') sir[i]=2; else sir[i]=3;
    for(i=1;i<=n;i++) for(j=i;j<=n;j++) dp[i][j]=(1<<30);
    for(pas=1;pas*2<=n;pas++)
        for(i=1;i+2*pas-1<=n;i++)
        {   j=i+pas-1; a[i][j]=0;
            for(k=i;k<j+pas;k++)
            {   memset(ap[k-i],0,sizeof(ap[k-i]));
                ap[k-i][sir[k]]=1;
            }
            nrper=1;
            for(j=i+2*pas-1;j<=n;j+=pas)
            {   nrper++; a[i][j]=0;
                for(k=0;k<pas;k++)
                {   ap[k][sir[j-pas+1+k]]++;
                    a[i][j]+=nrper-maxim(maxim(ap[k][0],ap[k][1]),maxim(ap[k][2],ap[k][3]));
                }
                if(a[i][j]<dp[i][j]) dp[i][j]=a[i][j];
            }
        }
    while(Q--) {f>>i>>j; g<<dp[i][j]<<'\n';}
    g.close(); return 0;
}