#include <bits/stdc++.h>

using namespace std;

const int Nmax = 600 + 10;
const int inf = 1e9;

int n , m , i , rest , lenght , j , cost , costP;
int a[Nmax] , ap[Nmax>>1][5] , dp[Nmax][Nmax];
int prec[Nmax];

char ch;

int minime(int r)
{
    vector < int > v; v.clear();
    for (int i = 1; i <= 4; ++i) v.push_back(ap[r][i]);
    sort(v.begin() , v.end());
    return (v[0] + v[1] + v[2]);
}

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

    scanf("%d %d\n", &n, &m);
    for (i = 1; i <= n; ++i)
    {
        scanf("%c", &ch);
        if (ch == 'A') a[i] = 1;
        else if (ch == 'C') a[i] = 2;
        else if (ch == 'G') a[i] = 3;
        else a[i] = 4;
    }

    for (i = 1; i <= n; ++i) for (j = i; j <= n; ++j) dp[i][j] = inf;

    for (lenght = 1; lenght <= (n >> 1); ++lenght)
    {
        for (int x = 0; x <= n; ++x) prec[x] = x % lenght;

        for (i = 1; i <= n - lenght + 1; ++i)
        {
            ///
            for (j = 0; j <= lenght; ++j) for (int k = 1; k <= 4; ++k) ap[j][k] = 0;

            for (j = i; j < i + (lenght << 1); ++j)
                ap[prec[j-i]][a[j]]++;
            j--;

            for (cost = 0, rest = 0; rest < lenght; ++rest)
                cost += minime(rest);
            dp[i][j] = min(dp[i][j] , cost);

            for (j = j + 1 ; j <= n; ++j)
            {
                ap[prec[j-i]][a[j]]++;

                if (!prec[j-i+1])
                {
                    for (cost = 0, rest = 0; rest < lenght; ++rest)
                        cost += minime(rest);

                    dp[i][j] = min(dp[i][j] , cost);
                }
            }
        }
    }

    for ( ; m ; --m)
    {
        int L , R;
        scanf("%d %d", &L, &R);
        printf("%d\n", dp[L][R]);
    }


    return 0;
}