#include<fstream>
using namespace std;
ifstream fi("perb.in");
ofstream fo("perb.out");
int n,m,i,j,k,poz,sum,x,y,A[605],Ap[605][605],Dp[605][605];
char S[605];
int main()
{
    fi>>n>>m;
    fi>>S;
    for(i=0; i<n; i++)
    {
        if(S[i]=='A')
            A[i+1]=1;
        if(S[i]=='C')
            A[i+1]=2;
        if(S[i]=='G')
            A[i+1]=3;
        if(S[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++)
    {
        for(j=1; j<=((n-i+1)/2); 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++)
    {
        fi>>x>>y;
        fo<<Dp[x][y]<<"\n";
    }
    fi.close();
    fo.close();
    return 0;
}