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

ifstream fin ("perb.in");
ofstream fout ("perb.out");
int d[DIM][DIM],p[DIM][DIM][5],v[DIM];
char s[DIM];
int n,q,x,y,i,j,t,dv,c,nr,nr1,nr2,nr3,nr4,cnt,poz;
vector <int> L[DIM];
int main (){

    fin>>n>>q;
    fin>>s+1;
    for (i=1;i<=n;i++){
        if (s[i] == 'A') v[i] = 1;
        if (s[i] == 'C') v[i] = 2;
        if (s[i] == 'G') v[i] = 3;
        if (s[i] == '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--;){
        fin>>x>>y;
        fout<<d[x][y]<<"\n";
    }

    return 0;
}