#include<stdio.h>

FILE *f = fopen("perb.in","r");
FILE *g = fopen("perb.out","w");

#define MaxN 700
#define MaxP 5

int N,M;
int A[MaxN],B[MaxP];
int Best[MaxN][MaxN];

void citire(void)
{
    char S[MaxN];

    fscanf(f,"%d %d\n",&N,&M);
    fgets(S,sizeof(S),f);
    for(int i=0;S[i]!='\n';)
        if(S[i] == 'A')
            A[++i] = 1;
        else if(S[i] == 'C')
            A[++i] = 2;
        else if(S[i] == 'G')
            A[++i] = 3;
        else if(S[i] == 'T')
            A[++i] = 4;
}

inline int min(int a,int b)
{
    return a < b ? a : b;
}

inline int carDel(int x,int y)
{
    int length = y-x+1,Min = 0;
    int modif,modifMin = 1<<29;

    for(int i=length>>1;i;i--)
        if(length%i == 0)
        {
            modif = 0;
            for(int j=0;j<i;j++)
            {
                B[1] = B[2] = B[3] = B[4] = 0;
                Min = 1<<29;
                for(int k=x+j;k<=y;k+=i)
                    ++ B[A[k]];
                for(int k=1;k<=4;k++)
                    Min = min(length/i-B[k],Min);
                modif += Min;
                if(modif > modifMin)
                    break;
            }
            modifMin = min(modifMin,modif);
        }

    return modifMin;
}

void initializare(void)
{
    for(int i=1;i<=N;i++)
        for(int j=i+1;j<=N;j++)
            Best[i][j] = -1;
}

void Rezolvare(void)
{
    int a,b;

    initializare();

    for(int i=1;i<=M;i++)
    {
        fscanf(f,"%d %d\n",&a,&b);
        if(Best[a][b] == -1)
            Best[a][b] = carDel(a,b);
        fprintf(g,"%d\n",Best[a][b]);
    }
}

int main()
{
    citire();
    Rezolvare();
}