#include <cstdio>
FILE *f,*g;
int v[1000];
int a[650][650];
int n,m,i,j,q,i1,j1,nr,cn,r,x,y;
int p[1000][5];
char c;


inline void reset() {
int i;
for (i=1;i<=n;i++)
     p[i][0]=p[i][1]=p[i][2]=p[i][3]=p[i][4]=0;

}

int main() {
f=fopen("perb.in","r");
g=fopen("perb.out","w");

fscanf(f,"%d%d",&n,&m);

while(c!='\n')
    fscanf(f,"%c",&c);

for (i=1;i<=n;i++) {
    fscanf(f,"%c",&c);
    switch (c) {
        case 'A' : v[i]=1; break;
        case 'C' : v[i]=2; break;
        case 'G' : v[i]=3; break;
        case 'T' : v[i]=4; break;
        break;
        }
    }

for (i=1;i<=n;i++)
    for (j=1;j<=n;j++)
        if (i==j)
            a[i][j]=0;
        else
            a[i][j]=-1;


for (i=1;i<=n;i++) {
    for (j=1;j<=n;j++) {
        i1=i; j1=i1+j; cn=1;

        if (i1+2*j<=n+1) {

            reset();

            for (nr=0,r=1,q=i1;q<j1;q++,r++) {
                    p[r][v[q]]++;
                    p[r][0]=p[r][v[q]];
                    }
            cn++;  i1=j1; j1=i1+j;

            while (j1<=n+1) {
                for (nr=0,r=1,q=i1;q<j1;q++,r++) {
                    p[r][v[q]]++;
                    if (p[r][v[q]]>p[r][0]) {
                        p[r][0]=p[r][v[q]];
                        nr=nr+(cn-p[r][0]);
                        }
                    else
                        nr=nr+(cn-p[r][0]);
                    }
                if (nr<a[i][j1-1] || a[i][j1-1]==-1)
                    a[i][j1-1]=nr;
                cn++;  i1=j1; j1=i1+j;
                }

            }

        }

    }


for (i=1;i<=m;i++) {
    fscanf(f,"%d%d",&x,&y);
    fprintf(g,"%d\n",a[x][y]);
    }


fclose(g);
return 0;
}