#include <fstream>
#include <cstring>
#define INF 2000000000
using namespace std;

int N, M;
char s[611];
int v[611];
int dp[611][611];
int cate[611][4];

int main ()
{
    ifstream fin ("perb.in");
    ofstream fout ("perb.out");
    fin >> N >> M >> s;
    for (int i = 0; i < N; i++)
    {
        if (s[i] == 'A') v[i] = 0;
        else if (s[i] == 'C') v[i] = 1;
        else if (s[i] == 'G') v[i] = 2;
        else v[i] = 3;
    }
    for (int i = 0; i < N; i++)
        for (int j = i + 1; j < N; j++)
            dp[i][j] = INF;
    for (int K = 1; K <= (N >> 1); K++)
    {
        for (int j = 0; j <= N; j++)
            memset (cate[j], 0, sizeof (cate[j]));
        for (int i = 0; i < K; i++)
            cate[i][v[i]] = 1;
        for (int i = K; i <= N; i++)
        {
            cate[i][0] = cate[i - K][0];
            cate[i][1] = cate[i - K][1];
            cate[i][2] = cate[i - K][2];
            cate[i][3] = cate[i - K][3];
            cate[i][v[i]]++;
        }
        cate[N][0]--;
        for (int i = 0; i + (K << 1) <= N; i++)
            for (int j = i + (K << 1); j <= N; j += K)
            {
                int dog = 0;
                for (int p = 1; p <= K; p++)
                    if (i - p < 0) dog += max (max (cate[j - p][0], cate[j - p][1]), max (cate[j - p][2], cate[j - p][3]));
                    else dog += max (max (cate[j - p][0] - cate[i - p][0], cate[j - p][1] - cate[i - p][1]), max (cate[j - p][2] - cate[i - p][2], cate[j - p][3] - cate[i - p][3]));
                dp[i][j - 1] = min (dp[i][j - 1], j - i - dog);
            }
    }
    for (int a, b; M; M--)
    {
        fin >> a >> b;
        fout << dp[a - 1][b - 1] << "\n";
    }
    fin.close ();
    fout.close ();
    return 0;
}