#include <cstdio>
#include <iostream>
#include <vector>
using namespace std;
int f[4],s[610],fp[610][610][4],idx[610];
vector <int> prim[610];
char buff[10001000];
int poz=0;
int solve (int l,int r,int len){
    int sol,i,j,maxi;
    sol=0;
    for (i=1;i<=len;i++){
        maxi = max (l-len+i-1,0);
        f[0] = fp[len][r - len + i][0] - fp[len][maxi][0];
        f[1] = fp[len][r - len + i][1] - fp[len][maxi][1];
        f[2] = fp[len][r - len + i][2] - fp[len][maxi][2];
        f[3] = fp[len][r - len + i][3] - fp[len][maxi][3];
        sol = sol + f[0] + f[1] + f[2] + f[3] - max(max (f[0],f[1]),max(f[2],f[3]));
    }
    return sol;
}
int getnr(){
    int nr=0;
    while ('0' > buff[poz] || buff[poz] > '9')
        poz ++;
    while ('0'<=buff[poz] && buff[poz]<='9'){
        nr = nr * 10 + buff[poz] - '0';
        poz ++;
    }
    return nr;
}
int main()
{
    FILE *fin=fopen ("perb.in","r");
    FILE *fout=fopen ("perb.out","w");
    int n,q,i,st,dr,l,d,sol;
    char c;
    fread (buff,1,10001000,fin);
    n = getnr();
    q = getnr();
    poz++;
    for (i=1;i<=n;i++){
        c= buff[poz];
        poz++;
        if (c=='A')
            s[i] = 0;
        else if (c=='C')
            s[i] = 1;
        else if (c=='G')
            s[i] = 2;
        else s[i] = 3;

    }
    for (i=1;i<=n;i++){
        l = i;
        d = 2;
        while (d*d<=l){
            if (l%d==0){
                prim[i].push_back(i/d);
                while (l%d==0)
                    l/=d;
            }
            d++;
        }
        if (l!=1 && l!=i)
            prim[i].push_back(i/l);
    }
    for (i=1;i<=n;i++){
        for (int j = 1;j<=n;j++){
            if (j-i>0){
                fp[i][j][0] = fp[i][j-i][0];
                fp[i][j][1] = fp[i][j-i][1];
                fp[i][j][2] = fp[i][j-i][2];
                fp[i][j][3] = fp[i][j-i][3];
            }
            fp[i][j][s[j]]++;
        }
    }
    //printf ("%d ",elem);
    for (;q;q--){
        st = getnr();
        dr = getnr();
        l = dr - st + 1;

        if (prim[l].empty()){ /// l = prim
            f[0] = fp[1][dr][0] - fp[1][st-1][0];
            f[1] = fp[1][dr][1] - fp[1][st-1][1];
            f[2] = fp[1][dr][2] - fp[1][st-1][2];
            f[3] = fp[1][dr][3] - fp[1][st-1][3];
            sol = f[0] + f[1] + f[2] + f[3] - max(max (f[0],f[1]),max(f[2],f[3]));
        }
        else {
            sol = n;
            for (int j=0;j<prim[l].size();j++)
                sol = min ( sol , solve (st,dr,prim[l][j]));
        }
        fprintf (fout,"%d\n",sol);

    }
    return 0;
}