#include <cstring>
#include <fstream>
#include <algorithm>

using namespace std;

const int INF = 0x3f3f3f3f;

int getcod(char C)
{
    if (C == 'A') return 0;
    if (C == 'C') return 1;
    if (C == 'G') return 2;
    return 3;
}

int N, M;
char C[602];
int per[602][602];
int maxm[602][4];

int main()
{
    ifstream fin("perb.in");
    ofstream fout("perb.out");

    fin >> N >> M >> C;

	for (int i = 1; i <= N; ++i)
		for (int j = i; j <= N; ++j)
			per[i][j] = INF;

	for (int i = 1; i <= N; ++i)
		for (int j = i; j <= N; ++j) // [i, j] este perioada
			if (j + 1 + (j - i + 1) - 1 <= N) // incape cel putin de doua ori
			{
				memset(maxm, 0, sizeof(maxm));
				for (int k = 1; k <= (j - i + 1); ++k)
					++maxm[k][getcod(C[i + k - 2])];
				for (int p = 2; j + (j - i + 1) * (p - 1) <= N; ++p)
				{
					for (int k = 1; k <= (j - i + 1); ++k)
						++maxm[k][getcod(C[i + (j - i + 1) * (p - 1) + k - 2])];
					
					int neednow = 0;
					for (int k = 1; k <= (j - i + 1); ++k)
					{
						int maxn = max(max(maxm[k][0], maxm[k][1]), max(maxm[k][2], maxm[k][3]));
						neednow += p - maxn;
					}
					
					per[i][j + (j - i + 1) * (p - 1)] = min(per[i][j + (j - i + 1) * (p - 1)], neednow);
				}
			}


    for (int i = 1, p1, p2; i <= M; ++i)
    {
        fin >> p1 >> p2;

        if (p1 == p2) fout << 0 << '\n';
        else          fout << per[p1][p2] << '\n';
    }

    fin.close();
    fout.close();
}