#include <cstring>
#include <cstdio>
#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][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");
    freopen("perb.out", "w", stdout);

    Ciur();

    fin >> N >> M >> C;

    for (int i = 2; i <= N; ++i)
    {
        int clone = i;
        for (int j = 1; prims[j] * prims[j] <= i; ++j)
            if (clone % prims[j] == 0)
            {
                facts[i][++facts[i][0]] = prims[j];
                while (clone % prims[j] == 0)
                    clone /= prims[j];
            }
        if (clone != 1) facts[i][++facts[i][0]] = clone;
    }

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

            fresult[p1][p2] = result;
        }

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

        if (p2 - p1 == 0) printf("0\n");
        else              printf("%d\n", fresult[p1][p2]);
    }

    fin.close();
}