#include <fstream>
#define nMax 604
#define INF 1000
using namespace std;
ifstream fin("perb.in");
ofstream fout("perb.out");
short int dp[nMax][nMax], a[nMax][4], vect[nMax], n, m, x, y, len, i, j, q, t, poz, rigt, cost, timee, Max, Mex[nMax];
char sir[nMax];
void Calcules()
{
    for(j=poz;j<=poz+len-1;j++)
    {
        a[j-poz][vect[j]]++;
        Mex[j-poz]=max(Mex[j-poz], a[j-poz][vect[j]]);
    }
    poz=j;
    for(j=0;j<len;j++)
        cost+=q-Mex[j];
    dp[i][poz-1]=min(dp[i][poz-1], cost);
}
int main()
{
    fin>>n>>m;
    fin>>(sir+1);
    for(i=1;i<=n;i++)
        switch(sir[i])
        {
            case 'A': vect[i]=0; break;
            case 'C': vect[i]=1; break;
            case 'G': vect[i]=2; break;
            case 'T': vect[i]=3; break;
        }
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
            dp[i][j]=INF;
    for(len=1;len<=n/2; len++)
    {
        for(i=1;i+len-1<=n;i++)
        {
            poz=i;
            q=1;
            timee=(n-i+1)/len;
            for(j=0;j<len;j++)
            {
                Mex[j]=0;
                for(t=0;t<4;t++)
                    a[j][t]=0;
            }
            Calcules();
            for(q=2;q<=timee;q++)
            {
                cost=0;
                rigt=poz+len-1;
                Calcules();
            }
        }
    }
    for(i=1;i<=m;i++)
    {
        fin>>x>>y;
        fout<<dp[x][y]<<'\n';
    }
    return 0;
}