#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 sub[Nmax][4];

int sums[Nmax][Nmax][4];

int primes[Nmax];
int countPrimes;

void genPrimes(int N) {
    for (int i = 2; i <= N; ++i) {
        int j, ok = 1;
        for (j = 2; j * j <= i; ++j) {
            if (i % j == 0) {
                ok = 0;
                break;
            }
        }

        if (ok) primes[countPrimes++] = i;
    }
}

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

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

    genPrimes(N);

    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:;
        }
    }

    int step;
    for (step = 1; step * 2 <= N; ++step) {
        int i, j;
        for (i = 0; i < step; ++i)
            for (j = 0; j < 4; ++j)
                sums[step][i][j] = values[i] == j;
        for (int i = step; i < N; ++i)
            for (int j = 0; j < 4; ++j)
                sums[step][i][j] = sums[step][i - step][j] + (values[i] == j);
    }

    FILL(dp, Inf);
    
    for (step = 1; step * 2 <= N; ++step) {
        int i;
        for (i = 0; i + 2 * step <= N; ++i) {
            int j;
            for (j = 0; j < step; ++j) {
                if (i - step + j >= 0) {
                    memcpy(sub[j], sums[step][i - step + j], sizeof(sub[j]));
                } else {
                    FILL(sub[j], 0);
                }
            }
            
            int k;
            for (k = 0; k < countPrimes && i + step * primes[k] <= N; ++k) {
                int begin = i + step * (primes[k] - 1);
                int cnt = primes[k];
                int ans = 0;
                for (j = 0; j < step; ++j) {
                    int l, max = 0;
                    for (l = 0; l < 4; ++l) {
                        int p = sums[step][begin + j][l] - sub[j][l];
                        if (max < p) max = p;
                    }
                    ans += cnt - max;
                }
                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]);
    }
}