#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][5], rest, vect[nMax], n, m, x, y, len, i, j, q, t, poz, rigt, cost, timee, Max, modo[nMax];
char sir[nMax];
int GO(int val)
{
    return max(max(a[val][1], a[val][2]), max(a[val][3], a[val][4]));
}
int main()
{
    fin>>n>>m;
    fin>>(sir+1);
    for(i=1;i<=n;i++)
        switch(sir[i])
        {
            case 'A': vect[i]=1; break;
            case 'C': vect[i]=2; break;
            case 'G': vect[i]=3; break;
            case 'T': vect[i]=4; break;
        }
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
            dp[i][j]=INF;
    for(len=1;len<=(n >> 1);len++)
    {
        for(i=1;i<=n;i++)
            modo[i]=i%len;
        for(i=1;i<=n-(len << 1)+1;i++)
        {
            for(j=0;j<len;j++)
                for(t=0;t<=4;t++)
                    a[j][t]=0;
            for(j=i;j<i+(len<<1);++j)
                a[modo[j-i]][0]++, a[modo[j-i]][vect[j]]++;
            j--;
            for(rest=0, cost=0;rest<len;rest++)
                cost+=a[rest][0]-GO(rest);
            dp[i][j]=min(dp[i][j], cost);
            for(j=j+1;j<=n;j++)
            {
                a[modo[j-i]][0]++, a[modo[j-i]][vect[j]]++;
                if(modo[j-i+1]==0)
                {
                    for(rest=0, cost=0;rest<len;rest++)
                        cost+=a[rest][0]-GO(rest);
                    dp[i][j]=min(dp[i][j], cost);
                }
            }
        }
    }
    for(i=1;i<=m;i++)
    {
        fin>>x>>y;
        fout<<dp[x][y]<<'\n';
    }
    return 0;
}