#include <bits/stdc++.h>

using namespace std;
ifstream f("perb.in");
ofstream g("perb.out");
int sol[605][605],fr[605][4],maxim[605],n,m,i,j,v2[605],pas,aux,ans,x,y,t;
char s[605];
int main()
{
    f>>n>>m;
    for (i=1;i<=n;i++)
    {
        f>>s[i];
    }
    for (i=1;i<=n;i++)
    {
        for (j=i+1;j<=n;j++)
        {
            sol[i][j]=1000000005;
        }
    }
    v2['A']=0;
    v2['C']=1;
    v2['G']=2;
    v2['T']=3;
    for (pas=1;pas<=n/2;pas++)
    {
        for (i=1;i<=n-pas+1;i++)
        {
            for (int k=1;k<=n;k++)
        {
            for (j=0;j<4;j++)
            {
                fr[k][j]=0;
            }
            maxim[k]=0;
        }
            ans=0;
            for (j=i;j<=i+pas-1;j++)
            {
                fr[j][v2[s[j]]]++;
                maxim[j]=max(maxim[j],fr[j][v2[s[j]]]);
            }
            aux=2;
            for (j=i+pas; j<=n; j++)
            {
                t = j - (aux - 1) * pas;
                fr[t][v2[s[j]]]++;
                maxim[t]=max(maxim[t],fr[t][v2[s[j]]]);
                ans = ans + (aux - maxim[t]);

                if (j-i+1 == aux * pas)
                {
                    sol[i][j] = min(sol[i][j], ans);
                    aux++;
                    ans=0;
                }
            }
        }
    }
    for (i=1;i<=m;i++)
    {
        f>>x>>y;
        g<<sol[x][y]<<'\n';
    }
    return 0;
}