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

int N, M;
int L[4], nr[maxn];
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() {
    fstream f1, f2;
    f1.open("perb.in", ios::in);
    f2.open("perb.out", ios::out);

    int i, j, p, q, asd;

    f1>>N>>M;
    f1>>A+1;

    for(i=1; i<=N; i++) {
         nr[i] = code(A[i]);
    }

    for(i=1; i<=N; i++) {
         memset(L, 0, sizeof(L));
         for(j=i; j<=N; j++) {
              L[ nr[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++) {
              for(p=0; p<j; p++) {
                   aux[p][0] = aux[p][1] = aux[p][2] = aux[p][3] = 0;
              }

              int nrper = (N - i + 1) / j;
              for(p=1; p<=nrper; p++) {
                   int val = j*(p-1);

                   for(q=i+val; q<i+j+val; q++) {
                        aux[q - i - val][ nr[q] ] ++;
                   }

                   if(p == 1) continue;

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

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

    for(i=1; i<=M; i++) {
         f1>>p>>q;
         f2<<sol[p][q]<<'\n';
    }

    f1.close(); f2.close();
    return 0;
}