#include <cstdio>
#include <iostream>
using namespace std;
int f[5],s[610],closest[610];
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 main()
{
    FILE *fin=fopen ("perb.in","r");
    FILE *fout=fopen ("perb.out","w");
    int n,q,i,st,dr,l,d,sol,x;
    char c;
    fscanf (fin,"%d%d\n",&n,&q);
    for (i=1;i<=n;i++){
        c= fgetc (fin);
        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)
                break;
            d++;
        }
        if (d*d>l)
            closest[l] = 1;
        else closest[l] = l/d;
    }
    for (;q;q--){
        fscanf (fin,"%d%d",&st,&dr);
        l = dr - st + 1;

        if (closest[l]==1){ /// l = prim
            sol = solve (st,dr,1);
        }
        else {
            sol = solve (st,dr,closest[l]); /// faci perioade cat mai mari
            d = l / closest[l];
            x = 1;
            while (l % (x*d) == 0)
                x = x * d;
            /// x = cea mai mare putere a lui d din l
            if (x * closest[l/x] != l)
                sol = min (sol , solve (st,dr,x * closest[l/x]));
        }
        fprintf (fout,"%d\n",sol);

    }
    return 0;
}