#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;

const int NMAX = 610;

int N, M, MinChanges[NMAX][NMAX], X, Y, Freq[NMAX][4], V[NMAX];
char S[NMAX];

int Max(int A, int B, int C, int D)
{
    return max(max(A, B), max(C, D));
}

int main()
{
    freopen("perb.in", "r", stdin);
    freopen("perb.out", "w", stdout);

    scanf("%i %i\n", &N, &M);

    for(int i = 1; i <= N; ++ i)
        for(int j = 1; j <= N; ++ j)
            MinChanges[i][j] = 0x3f3f3f3f;

    gets(S + 1);
    for(int i = 1; i <= N; ++ i)
    {
        if(S[i] == 'A') V[i] = 0;
        else if(S[i] == 'C') V[i] = 1;
        else if(S[i] == 'G') V[i] = 2;
        else V[i] = 3;
    }

    for(int Period = 1; Period <= N; Period ++)
        for(int Left = 1; Left + 2 * Period - 1 <= N; ++ Left)
        {
            int NrSecv = 1, Now = 0, R = 0;

            for(int Right = Left; Right <= N; Right ++)
            {
                R ++;
                if(R == Period) R = 0;

                if(NrSecv == 1) Freq[R][0] = Freq[R][1] = Freq[R][2] = Freq[R][3] = 0;

                Freq[R][V[Right]] ++;

                Now += NrSecv - Max(Freq[R][0], Freq[R][1], Freq[R][2], Freq[R][3]);
                if(R == 0)
                {
                    if(NrSecv > 1) MinChanges[Left][Right] = min(MinChanges[Left][Right], Now);
                    Now = 0;
                    NrSecv ++;
                }
            }
        }

    for(; M; M --)
    {
        scanf("%i %i", &X, &Y);
        printf("%i\n", MinChanges[X][Y]);
    }
}