#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, time, Max;
char sir[nMax];
int code(char ch)
{
    if(ch=='A')
        return 0;
    if(ch=='C')
        return 1;
    if(ch=='G')
        return 2;
    if(ch=='T')
        return 3;
}
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; len++)
    {
        for(i=1;i+len-1<=n;i++)
        {
            for(j=0;j<len;j++)
                for(t=0;t<4;t++)
                    a[j][t]=0;
            time=(n-i+1)/len;
            poz=i;
            for(j=poz;j<=i+len-1;j++)
                a[j-poz][vect[j]]++;
            poz=j;
            for(q=2;q<=time;q++)
            {
                cost=0;
                rigt=poz+len-1;
                for(j=poz;j<=rigt;j++)
                    a[j-poz][vect[j]]++;
                poz=j;
                for(j=0;j<len;j++)
                {
                    Max=0;
                    for(t=0;t<4;t++)
                        Max=max(Max, a[j][t]);
                    cost+=q-Max;
                }
                dp[i][poz-1]=min(dp[i][poz-1], cost);
            }
        }
    }
    for(i=1;i<=m;i++)
    {
        fin>>x>>y;
        fout<<dp[x][y]<<'\n';
    }
    return 0;
}