#include <stdio.h>

int n, t;
char s[605];
int sol[605][605], nr[605][605];

char ch[] = {"ACGT"};

inline int max (int a, int b) {return a > b ? a : b;}

void rez (int p)
{
    int i, j, k, c, dif, cost;

    for (i = n; i >= 1; i --)
        for (j = 0; j < 4; j ++)
            if (i + p > n)
                nr[i][j] = (s[i] == ch[j]);
            else
                nr[i][j] = nr[i + p][j] + (s[i] == ch[j]);

    for (i = 1; i <= n; i ++)
        for (j = i + 2 * p - 1; j <= n; j += p)
        {
            cost = 0;

            for (k = 0; k < p; k ++)
            {
                dif =           nr[i + k][0] - nr[j + k + 1][0];
                dif = max (dif, nr[i + k][1] - nr[j + k + 1][1]);
                dif = max (dif, nr[i + k][2] - nr[j + k + 1][2]);
                dif = max (dif, nr[i + k][3] - nr[j + k + 1][3]);

                cost = cost + ((j - i + 1) / p - dif);
            }

            if (!sol[i][j] || cost < sol[i][j])
                sol[i][j] = cost;
        }
}

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

    scanf ("%d %d\n", &n, &t);
    gets (s + 1);

    int i, x, y;

    for (i = 1; i <= n / 2; i ++)
        rez (i);

    while (t --)
    {
        scanf ("%d %d", &x, &y);
        printf ("%d\n", sol[x][y]);
    }
    return 0;
}