#include <fstream>
#include <cstring>
using namespace std;
ifstream f("perb.in");
ofstream g("perb.out");
int d[605][605],n,m,i,j,l,x,y,sol,per,p[51],fr[601][4],maxi[601];
char S[605];
int main()
{   f>>n>>m;
    f>>(S+1);
    p['A'-'A']=0;
    p['C'-'A']=1;
    p['G'-'A']=2;
    p['T'-'A']=3;
    for(i=1;i<=n;i++)
        for(j=i+1;j<=n;j++)
            d[i][j]=n+1;
    for(l=1;l<=n/2;l++){
        for(i=1;i<=n-l+1;i++){
            per=1;
            memset(fr,0,sizeof(fr));
            memset(maxi,0,sizeof(maxi));
            for(j=i;j<=i+l-1;j++){
                int a=p[S[j]-'A'];
                int b=j-(per-1)*l;
                fr[b][a]++;
                maxi[b]=max(maxi[b],fr[b][a]);
            }
            per=2;sol=0;
            for(j=i+l;j<=n;j++){
                int a=p[S[j]-'A'];
                int b=j-(per-1)*l;
                fr[b][a]++;
                maxi[b]=max(maxi[b],fr[b][a]);
                sol+=per-maxi[b];
                if(j-i+1==per*l){
                    d[i][j]=min(d[i][j],sol);
                    per++;
                    sol=0;
                }
            }
        }
    }
    for(i=1;i<=m;i++){
        f>>x>>y;
        if(x>y)
            swap(x,y);
        g<<d[x][y]<<'\n';
    }
    return 0;
}