#include <bits/stdc++.h>

using namespace std;

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

int n , m , i , rest , lengBAGPULA , j , cost , costP;
int a[Nmax] , ap[Nmax][6] , dp[Nmax][Nmax];
int prec[Nmax];

char ch;

int minime(int r)
{
    return (max(max(ap[r][1] , ap[r][2]) , max(ap[r][3] , ap[r][4])));
}

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 (lengBAGPULA = 1; lengBAGPULA <= (n >> 1); ++lengBAGPULA)
    {
        for (int x = 0; x <= n; ++x) prec[x] = x % lengBAGPULA;

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

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

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

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

                if (!prec[j-i+1])
                {
                    for (cost = 0, rest = 0; rest < lengBAGPULA; ++rest)
                        cost += ap[rest][0] - 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;
}