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

using namespace std;

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

int N, M;
int prims[1002], prim[1002];
char C[606];
int facts[606], freq[4];
int fresult[606][606];

void Ciur()
{
    prims[++prims[0]] = 2;
    for (int i = 3; i <= 600; i += 2)
        if (!prim[i])
        {
            prims[++prims[0]] = i;
            for (int j = i * i; j <= 600; j += 2 * i)
                prim[j] = true;
        }
}

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

    Ciur();

    fin >> N >> M >> C;

    for (int p1 = 1; p1 <= N; ++p1)
        for (int p2 = p1; p2 <= N; ++p2)
        {
            facts[0] = 0;
            int size = p2 - p1 + 1, clone = size, result = 1 << 30;
            for (int j = 1; prims[j] * prims[j] <= size; ++j)
                if (clone % prims[j] == 0)
                {
                    facts[++facts[0]] = prims[j];
                    while (clone % prims[j] == 0)
                        clone /= prims[j];
                }
            if (clone != 1) facts[++facts[0]] = clone;

            for (int i = 1; i <= facts[0]; ++i)
            {
                int resultnow = 0;
                for (int k = 1; k <= size / facts[i]; ++k)
                {
                    memset(freq, 0, sizeof(freq));
                    for (int j = p1 + k - 1; j <= p2; j += size / facts[i])
                        ++freq[getcod(C[j - 1])];
                    int maxim = max(max(freq[0], freq[1]), max(freq[2], freq[3]));
                    resultnow += facts[i] - maxim;
                }
                result = min(result, resultnow);
            }

            fresult[p1][p2] = result;
        }

    for (int i = 1, p1, p2; i <= M; ++i)
    {
        fin >> p1 >> p2;
        fout << fresult[p1][p2] << '\n';
    }

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