#include <fstream>
#include <cstdio>
#include <vector>
#define INF 2000000000
#define DIM 610
#define DIMBUFF 5000000
using namespace std;

//ifstream fin ("perb.in");
//ofstream fout ("perb.out");
FILE *fin = fopen ("perb.in","r");
FILE *fout = fopen ("perb.out","w");
int d[DIM][DIM],p[DIM][DIM][5],v[DIM];
char s[DIM],buff[DIMBUFF],ch;
int n,q,x,y,i,j,t,dv,c,nr,nr1,nr2,nr3,nr4,cnt,poz,pos;
vector <int> L[DIM];
inline int get_nr(){
    while (!(buff[pos] >= '0' && buff[pos] <= '9'))
        pos++;
    int nr = 0;
    while (buff[pos] >= '0' && buff[pos] <= '9'){
        nr = nr*10 + buff[pos] - '0';
        pos++;
    }
    return nr;
}
inline char get_ch(){
    while (!(buff[pos] == 'A' || buff[pos] == 'C' || buff[pos] == 'G' || buff[pos] == 'T'))
        pos++;

}
int main (){

    fread (buff,1,DIMBUFF,fin);
    n = get_nr(), q = get_nr();
    pos++;
    for (i=1;i<=n;i++){
        ch = buff[pos], pos++;
        if (ch == 'A') v[i] = 1;
        if (ch == 'C') v[i] = 2;
        if (ch == 'G') v[i] = 3;
        if (ch == 'T') v[i] = 4;
    }
    /// p[i][j][c] - cate caractere c sunt plecand de la pozitia i in spate din j in j
    for (i=1;i<=n;i++)
        for (j=1;j<=n;j++)
            for (c=1;c<=4;c++){
                if (i > j)
                    p[i][j][c] = p[i-j][j][c];
                if (c == v[i])
                    p[i][j][c]++;
            }

    for (i=1;i<=n;i++)
        for (dv=1;dv*dv<=i;dv++)
            if (i%dv == 0){
                L[i].push_back(dv);
                if (i/dv != i)
                    L[i].push_back(i/dv);
            }
    for (i=1;i<=n;i++)
        for (j=1;j<=n;j++)
            d[i][j] = INF;

    for (i=1;i<n;i++)
        for (j=i+1;j<=n;j++){
            nr = j-i+1;
            for (t=0;t<L[nr].size();t++){
                /// incerc sa gasesc nr minim de transformi ale secventei intr una periodica de lg un divizor
                int lg = L[nr][t];
                int nr_modif = 0;
                for (poz=j,cnt=1;poz>=j-lg+1;poz--,cnt++){
                    nr1 = p[poz][lg][1];
                    nr2 = p[poz][lg][2];
                    nr3 = p[poz][lg][3];
                    nr4 = p[poz][lg][4];
                    if (i > cnt){
                        nr1 -=  p[i-cnt][lg][1];
                        nr2 -=  p[i-cnt][lg][2];
                        nr3 -=  p[i-cnt][lg][3];
                        nr4 -=  p[i-cnt][lg][4];
                    }
                    nr_modif += nr/lg - max(max(nr1,nr2),max(nr3,nr4));
                }
                d[i][j] = min (d[i][j],nr_modif);
            }}
    for (;q--;){
        x = get_nr(), y = get_nr();
        fprintf(fout,"%d\n",d[x][y]);
    }

    return 0;
}