#include<cstdio>
#include<cstring>
using namespace std;
int nrper,k,i,j,pas,INF,n,Q,dp[603][603],a[603][603],ap[603][5];
char sir[603];
int max(int a,int b){if(a<b) return b;return a;}
int main()
{
freopen("perb.in","r",stdin);
freopen("perb.out","w",stdout);
INF=(1<<30);
scanf("%d",&n);
scanf("%d\n",&Q);
gets(sir+1);
for(i=1;i<=n;i++)
{
    if(sir[i]=='A') sir[i]=0;
    else
    if(sir[i]=='T') sir[i]=1;
    else
    if(sir[i]=='C') sir[i]=2;
    else sir[i]=3;
}
for(i=1;i<=n;i++)
    for(j=i;j<=n;j++)
        dp[i][j]=INF;
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-max(max(ap[k][0],ap[k][1]),max(ap[k][2],ap[k][3]));
            }
            if(a[i][j]<dp[i][j]) dp[i][j]=a[i][j];
        }
    }
while(Q)
{
    Q--;
    scanf("%d %d",&i,&j);
    printf("%d\n",dp[i][j]);
}
return 0;
}