#include<fstream>
#include<stdio.h>
#include<string.h>
using namespace std;
FILE *fi=fopen("perb.in","r");
ofstream fo("perb.out");
int n,m,i,j,k,poz,sum,x,y,A[605],Ap[605][605],Dp[605][605],aux;
char St[605];
char S[500005];
int l,ind;

void nextS()
{
    ind=0;
    fread(S,1,500000,fi);
    l=strlen(S);
}

int nextInt()
{
    int r=0;
    if(ind==l)
        nextS();
    while(S[ind]<'0' || S[ind]>'9')
    {
        ind++;
        if(ind==l)
            nextS();
    }
    while(S[ind]>='0' && S[ind]<='9')
    {
        r=r*10+S[ind]-'0';
        ind++;
        if(ind==l)
            nextS();
    }
    return r;
}

int main()
{
    fscanf(fi,"%d%d",&n,&m);
    fscanf(fi,"%s",&St);
    for(i=0; i<n; i++)
    {
        if(St[i]=='A')
            A[i+1]=1;
        if(St[i]=='C')
            A[i+1]=2;
        if(St[i]=='G')
            A[i+1]=3;
        if(St[i]=='T')
            A[i+1]=4;
    }
    for(i=1; i<=n; i++)
        for(j=i; j<=n; j++)
            Dp[i][j]=1000000000;
    for(i=1; i<=n; i++)
    {
        aux=((n-i+1)/2);
        for(j=1; j<=aux; j++)
        {
            for(k=0; k<j; k++)
                Ap[k][1]=Ap[k][2]=Ap[k][3]=Ap[k][4]=0;
            sum=0;
            for(k=i; k<=n; k++)
            {
                poz=(k-i+1)%j;
                Ap[poz][A[k]]++;
                sum=sum+Ap[poz][1]+Ap[poz][2]+Ap[poz][3]+Ap[poz][4]-max(max(Ap[poz][1],Ap[poz][2]),max(Ap[poz][3],Ap[poz][4]));
                if(poz==0)
                {
                    if((k-i+1)/j>1)
                        Dp[i][k]=min(Dp[i][k],sum);
                    sum=0;
                }
            }
        }
    }
    for(i=1; i<=m; i++)
    {
        x=nextInt();
        y=nextInt();
        fo<<Dp[x][y]<<"\n";
    }
    fclose(fi);
    fo.close();
    return 0;
}