#include <algorithm>
#include <cstdio>
using namespace std;

int n, m, best[605][605], dif[605][128];
char s[605];
int main()
{
    freopen("perb.in", "r", stdin);
    freopen("perb.out", "w", stdout);
    scanf("%d%d", &n, &m);
    scanf("%s", s + 1);
    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 + 1 ; ++d){
            for(int j = 0; j < d ; ++j) dif[j]['A'] = dif[j]['C'] = dif[j]['G'] = dif[j]['T'] = 0;
            int aux = 0, rest = 0;
            for(int j = i; j <= n ; ++j){
                ++rest;
                if(rest == d) rest = 0;
                aux = aux - (dif[rest]['A'] + dif[rest]['C'] + dif[rest]['G'] + dif[rest]['T'] - max(max(dif[rest]['A'], dif[rest]['C']), max(dif[rest]['G'], dif[rest]['T'])));
                ++dif[rest][s[j]];
                aux = aux + (dif[rest]['A'] + dif[rest]['C'] + dif[rest]['G'] + dif[rest]['T'] - max(max(dif[rest]['A'], dif[rest]['C']), max(dif[rest]['G'], dif[rest]['T'])));
                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;
}