#include <stdio.h>
#include <string.h>
#define FILL(x, y) memset((x), (y), sizeof (x))
#define Nmax 610
#define Inf 0x3f3f3f3f

char A[Nmax];
int values[Nmax];

int dp[Nmax][Nmax];
int count[Nmax][4];

int max(int a[4]) {
    int v = a[0], i;
    for (i = 1; i < 4; ++i)
        if (v < a[i])
            v = a[i];
    return v;
}

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

    int N, Q;
    scanf("%d%d", &N, &Q);

    scanf("%s", A);
    int i;
    for (i = 0; i < N; ++i) {
        switch(A[i]) {
            case 'A': values[i] = 0; break;
            case 'C': values[i] = 1; break;
            case 'G': values[i] = 2; break;
            case 'T': values[i] = 3; break;
            default:;
        }
    }

    FILL(dp, Inf);
    
    int step;
    for (step = 1; step * 2 <= N; ++step) {
        int i;
        for (i = 0; i + 2 * step <= N; ++i) {
            memset(count, 0, step * sizeof(int[4]));
            int j;
            for (j = 0; j < step; ++j)
                count[j][values[i + j]]++;
            
            int begin, cnt = 1;
            for (begin = i + step; begin <= N - step; begin += step) {
                cnt++;
                int ans = 0;
                for (j = 0; j < step; ++j) {
                    count[j][values[begin + j]]++;
                    ans += cnt - max(count[j]);
                }
                int end = begin + step;
                if (dp[i][end] > ans) dp[i][end] = ans;
            }
        }
    }

    while (Q-- > 0) {
        int left, right;
        scanf("%d%d", &left, &right);
        
        printf("%d\n", dp[left - 1][right]);
    }
}