#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];

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 i = 1, p1, p2; i <= M; ++i)
    {
        fin >> p1 >> 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);
        }

        fout << result << '\n';
    }

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