#include <fstream>
#include <vector>
#include <algorithm>
#include <cstring>

using namespace std;

ifstream cin("perb.in");
ofstream cout("perb.out");

const int MAXN = 600;
const int SIGMA = 4;

char s[1 + MAXN];
int letters[1 + MAXN][SIGMA], dp[1 + MAXN][1 + MAXN];

int F(int x) {
    return max(letters[x][0], max(letters[x][1], max(letters[x][2], letters[x][3])));
}

int main() {
    int n, m;
    cin >> n >> m >> s + 1;
    for (int i = 1; i <= n; i++) {
        if (s[i] == 'A')
            s[i] = 0;
        if (s[i] == 'C')
            s[i] = 1;
        if (s[i] == 'G')
            s[i] = 2;
        if (s[i] == 'T')
            s[i] = 3;
    }
    for (int i = 1; i <= n; i++)
        for (int j = i + 1; j <= n; j++)
            dp[i][j] = j - i;
    for (int i = 1; i <= n / 2; i++)
        for (int j = 1; j + 2 * i - 1 <= n; j ++) {
            memset(letters, 0, sizeof(letters));
            int length = 0, times = 0;
            for (int k = j; k <= n; k++) {
                length++;
                if (length > i)
                    length -= i;
                letters[length][s[k]]++;
                if (length == i) {
                    times++;
                    int answer = 0;
                    for (int l = 1; l <= i; l++)
                        answer = answer + times - F(l);
                    if (times != 1)
                        dp[j][k] = min(dp[j][k], answer);
                }
            }
        }
    for (int i = 1; i <= m; i++) {
        int a, b;
        cin >> a >> b;
        cout << dp[a][b] << "\n";
    }
    return 0;
}