#include <bits/stdc++.h>

using namespace std;

ifstream f ("perb.in");
ofstream g ("perb.out");

int n, m;

char s[605];

int sol[605][605];
int fr[605][5];

int x[30];
int Max[605];

int main()
{
    f >> n >> m;

    for (int i=1; i<=n; ++i)
        f >> s[i];

    for (int i=1; i<=n; ++i)
        for (int j=i+1; j<=n; ++j)
            sol[i][j] = 1e9;

    x['c'-'a']=1;
    x['g'-'a']=2;
    x['t'-'a']=3;
    for (int d=1; d<=n/2; ++d)
    {
        for (int i=1; i<=n-d+1; ++i)
        {
            memset(fr, 0, sizeof(fr));
            memset(Max, 0, sizeof(Max));
            int ans=0;
            for (int j=i; j<=i+d-1; ++j)
            {
                fr[j][x[s[j]-'A']]++;
                Max[j] = max(Max[j], fr[j][x[s[j]-'A']]);
            }

            int aux=2;

            for (int j=i+d; j<=n; ++j)
            {
                int t = j - (aux - 1) * d;
                fr[t][x[s[j]-'A']]++;
                Max[t] = max(Max[t], fr[t][x[s[j]-'A']]);
                ans = ans + (aux - Max[t]);

                if (j-i+1 == aux * d)
                {
                    sol[i][j] = min(sol[i][j], ans);
                    aux++;
                    ans=0;
                }
            }
        }
    }

    for (int i=1; i<=m; ++i)
    {
        int st, dr;
        f >> st >> dr;

        g << sol[st][dr] << '\n';
    }
    return 0;
}