#include <bits/stdc++.h>

#define MAX_N 600

#define MAX_CHR 4
#define MAX_CHAR 26

using namespace std;

const int sqrInf = (1e9) - 1;

ifstream f("perb.in");

string s;

int n, m;

int v[MAX_N + 1];
int dp[MAX_N + 1][MAX_N + 1];

int ap[MAX_N + 1][MAX_CHR + 1];
int mx[MAX_N + 1];
int cod[MAX_CHAR + 1];

int modd[MAX_N + 1][MAX_N + 1];

void readFile()
{
    f >> n >> m;

    f >> s;
}

void init0()
{
    int i, j;
    for(i = 1; i <= n; i ++)
    {
        for(j = i + 1; j <= n; j ++)
            dp[i][j] = sqrInf;
    }
}

void getModd()
{
    int i, j;
    for(i = 1; i <= n; i ++)
    {
        for(j = 1; j <= n; j ++)
            modd[i][j] = (i % j != 0 ? i % j : j);
    }
}

void solve()
{
    init0();

    getModd();

    cod['A' - 'A'] = 1;
    cod['C' - 'A'] = 2;
    cod['G' - 'A'] = 3;
    cod['T' - 'A'] = 4;

    int i, j, t;
    for(i = 0; i < n; i ++)
        v[i + 1] = cod[s[i] - 'A'];

    for(t = 1; t < n; t ++)
    {
        for(i = 1; i + (t << 1) - 1 <= n; i ++)
        {
            int cost = 0;

            for(int h = 1; h <= t; h ++)
                memset(ap[h], 0, sizeof(ap[h]));

            memset(mx, 0, (t << 2));

            for(j = i; j <= n; j ++)
            {
                int poz = j - i + 1;
                int per = modd[poz][t];

                ap[per][v[j]] ++;

                if(mx[per] == v[j])
                    cost ++;

                else
                    if(ap[per][v[j]] > ap[per][mx[per]])
                    {
                        cost -= ap[per][mx[per]];
                        cost += ap[per][v[j]];
                        mx[per] = v[j];
                    }

                if(per == t && poz >= (t << 1))
                    dp[i][j] = min(dp[i][j], poz - cost);
            }
        }
    }
}

void printFile()
{
    ofstream g("perb.out");

    while(m > 0)
    {
        m --;

        int a, b;
        f >> a >> b;
        g << dp[a][b] << "\n";
    }

    g.close();
}

int main()
{
    readFile();

    solve();

    printFile();

    return 0;
}