#include <bits/stdc++.h>
using namespace std;

int n, m, best[605][605], dif[605][4];
char s[605];
inline int f(char c){
    if(c == 'A') return 0;
    if(c == 'C') return 1;
    if(c == 'G') return 2;
    if(c == 'T') return 3;
}
int main()
{
    freopen("perb.in", "r", stdin);
    freopen("perb.out", "w", stdout);
    scanf("%d%d\n", &n, &m);
    for(int i = 1; i <= n ; ++i)
        s[i] = getchar();
    for(int i = 1; i <= n ; ++i)
        for(int j = i; j <= n ; ++j)
            best[i][j] = j - i + 1;
    for(int i = 1; i < n ; ++i){
        for(int d = 1; d <= n - i ; ++d){
            memset(dif, 0, sizeof(dif));
            int aux = 0, rest = 0;
            for(int j = i; j <= n ; ++j){
                ++rest;
                if(rest == d) rest = 0;
                aux = aux - (dif[rest][0] + dif[rest][1] + dif[rest][2] + dif[rest][3] - max(max(dif[rest][0], dif[rest][1]), max(dif[rest][2], dif[rest][3])));
                ++dif[rest][f(s[j])];
                aux = aux + (dif[rest][0] + dif[rest][1] + dif[rest][2] + dif[rest][3] - max(max(dif[rest][0], dif[rest][1]), max(dif[rest][2], dif[rest][3])));
                if(rest == 0 && j - i + 1 > d) best[i][j] = min(best[i][j], aux);
            }
        }
    }
    int l, r;
    for(int i = 1; i <= m ; ++i){
        scanf("%d%d", &l, &r);
        printf("%d\n", best[l][r]);
    }
    return 0;
}