#include <fstream>
#include <cstring>
#include <algorithm>
#include <cassert>

using namespace std;

const int MaxN = 605;

ifstream fin("perb.in");

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

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

inline void InitPer(int Per[MaxN][4], const int L) {
    for (int i = 0; i < L; ++i)
        for (int c = 0; c < 4; ++c)
            Per[i][c] = 0;
}

inline void UpdatePer(int Per[MaxN][4], const int Start, const int L, int &Cost) {
    Cost = 0;
    for (int i = 0; i < L; ++i) {
        ++Per[i][GetCode(String[Start+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);
    }
}

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

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

void Read() {
    fin >> N >> NQ >> String;
}

void Print() {
    ofstream fout("perb.out");
    for (; NQ; --NQ) {
        int X, L; fin >> X >> L;
        L = L-X+1; --X;
        fout << DP[X][L] << "\n";
    }
    fin.close();
    fout.close();
}

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