#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 i = 0; i < N; i++)
        for (int K = 1; K <= ((N - i) >> 1); K++)
        {
            for (int j = 0; j < N; j++)
                memset (cate[j], 0, sizeof (cate[j]));
            for (int j = i, rest = 1; j < N; j++, rest++)
            {
                if (rest == K) rest = 0;
                cate[rest][v[j]]++;
                int a = j - i + 1;
                if (a % K == 0 && a > K)
                {
                    int dog = 0;
                    for (int p = 0; p < K; p++)
                        dog += max (max (cate[p][0], cate[p][1]), max (cate[p][2], cate[p][3]));
                    dp[i][j] = min (dp[i][j], j - i + 1 - dog);
                }
            }
        }
    for (int a, b; M; M--)
    {
        fin >> a >> b;
        fout << dp[a - 1][b - 1] << "\n";
    }
    fin.close ();
    fout.close ();
    return 0;
}