#include <fstream>
#define nMax 604
#define INF 1000
using namespace std;
ifstream fin("perb.in");
ofstream fout("perb.out");
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 ch;
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;
    for (i = 1; i <= n; ++i)
    {
        fin>>ch;
        if (ch == 'A') vect[i] = 1;
        else if (ch == 'C') vect[i] = 2;
        else if (ch == 'G') vect[i] = 3;
        else vect[i] = 4;
    }
    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;
}