#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cassert>

using namespace std;

const int MaxN = 605;

int N, NQ, DP[MaxN][MaxN];
char String[MaxN];

inline int GetCode(char C) {
    if (C == 'A')
        return 0;
    if (C == 'G')
        return 1;
    if (C == 'C')
        return 2;
    return 3;
}

inline void UpdatePer(int Per[MaxN][4], const int Start, const int L) {
    for (int i = 0; i < L; ++i)
        ++Per[i][GetCode(String[Start+i])];
}

inline int GetCost(int Per[MaxN][4], int L) {
    int Cost = 0;
    for (int i = 0; i < L; ++i) {
        int MaxC = 0, TotalC = 0;
        for (int c = 0; c < 4; ++c)
            TotalC += Per[i][c], MaxC = max(MaxC, Per[i][c]);
        Cost += (TotalC-MaxC);
    }
    return Cost;
}

inline void MakePeriod(const int Start, const int L) {
    int Per[MaxN][4]; memset(Per, 0, sizeof(Per));
    UpdatePer(Per, Start, L);
    for (int k = 2; Start+k*L-1 < N; ++k) {
        UpdatePer(Per, Start+(k-1)*L, L);
        DP[Start][k*L] = min(DP[Start][k*L], GetCost(Per, L));
    }
}

void Solve() {
    memset(DP, 0x3f, sizeof(DP));
    for (int i = 0; i < N; ++i) {
        DP[i][1] = 0;
        for (int L = 1; i+L-1 < N; ++L)
            MakePeriod(i, L);
    }
}

void Read() {
    assert(freopen("perb.in", "r", stdin));
    assert(scanf("%d %d\n%s", &N, &NQ, String) == 3);
}

void Print() {
    assert(freopen("perb.out", "w", stdout));
    for (; NQ; --NQ) {
        int X, L; assert(scanf("%d %d", &X, &L) == 2);
        L = L-X+1; --X;
        printf("%d\n", DP[X][L]);
    }
}

int main() {
    Read();
    Solve();
    Print();
    return 0;
}