#include <cstdio>
#include <iostream>
#include <vector>
using namespace std;
int f[5],s[610],fp[610][4];
vector <int> prim[610];
char buff[10001000];
int poz=0;
int solve (int l,int r,int len){
    int sol,i,j;
    sol=0;
    for (i=1;i<=len;i++){
        f[0]=f[1]=f[2]=f[3]=0;
        for (j=l+i-1;j<=r;j+=len)
            f[s[j]]++;
        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;
        fp[i][0] = fp[i-1][0];
        fp[i][1] = fp[i-1][1];
        fp[i][2] = fp[i-1][2];
        fp[i][3] = fp[i-1][3];
        fp[i][s[i]]++;
    }
    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 (;q;q--){
        st = getnr();
        dr = getnr();
        l = dr - st + 1;

        if (prim[l].empty()){ /// l = prim
            f[0] = fp[dr][0] - fp[st-1][0];
            f[1] = fp[dr][1] - fp[st-1][1];
            f[2] = fp[dr][2] - fp[st-1][2];
            f[3] = fp[dr][3] - fp[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;
}