#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
#define maxn 610

int N, M;
int L[4];
int aux[maxn][4];
int sol[maxn][maxn];
char A[maxn];

int code(char c) {
    if(c == 'G') return 0;
    if(c == 'C') return 1;
    if(c == 'A') return 2;
    if(c == 'T') return 3;
}

int main() {
    FILE *f1=fopen("perb.in", "r"), *f2=fopen("perb.out", "w");
    int i, j, p, q;

    fscanf(f1, "%d %d\n", &N, &M);
    fscanf(f1, "%s\n", A+1);

    for(i=1; i<=N; i++) {
         memset(L, 0, sizeof(L));
         for(j=i; j<=N; j++) {
              L[ code(A[j]) ] ++;

              int mx = 0;
              for(p=0; p<=3; p++) {
                   mx = max(mx, L[p]);
              }

              sol[i][j] = j - i + 1 - mx;
         }
    }

    for(i=1; i<=N; i++) {
         int per = (N - i + 1) / 2;
         for(j=2; j<=per; j++) {
              memset(aux, 0, sizeof(aux));

              int nrper = (N - i + 1) / j;
              for(p=1; p<=nrper; p++) {
                   for(q=i+j*(p-1); q<i+j*p; q++) {
                        aux[q - i - j*(p-1)][ code(A[q]) ] ++;
                   }

                   if(p == 1) continue;

                   int jeg = 0;
                   for(q=i+j*(p-1); q<i+j*p; q++) {
                        int mx = 0;
                        for(int asd=0; asd<=3; asd++) {
                             mx = max(mx, aux[q - i - j*(p-1)][asd]);
                        }
                        jeg += (p-mx);
                   }

                   sol[i][i+j*p-1] = min(sol[i][i+j*p-1], jeg);
              }
         }
    }

    for(i=1; i<=M; i++) {
         fscanf(f1, "%d %d\n", &p, &q);
         fprintf(f2, "%d\n", sol[p][q]);
    }

    fclose(f1); fclose(f2);
    return 0;
}