#include <bits/stdc++.h>
#define Nmax 605
#define INF 2000000000

using namespace std;

int sol[Nmax][Nmax],fr[Nmax][4],mx[Nmax],n,xx[Nmax],yy[Nmax];
char a[Nmax];
bool seen[Nmax];

inline int cod(char x)
{
    if(x=='A') return 0;
    if(x=='C') return 1;
    if(x=='G') return 2;
    if(x=='T') return 3;
}

int main()
{
    int x,y,i,j,jj,d,k,Q,sum;
    ifstream cin("perb.in");
    ofstream cout("perb.out");
    cin>>n>>Q>>(a+1);
    for(i=1;i<=Q;++i)
    {
        cin>>xx[i]>>yy[i]; seen[xx[i]]=true;
    }
    for(i=1;i<=n;++i)
        for(j=i;j<=n;++j) sol[i][j]=INF;
    for(i=1;i<=n;++i)
    {
        if(!seen[i]) continue;
        for(d=1;d<=(n-i+1)/2;++d)
        {
            for(j=1;j<=d;++j) fr[j][0]=fr[j][1]=fr[j][2]=fr[j][3]=0;
            for(j=i+d-1;j<=n;j+=d)
            {
                for(k=j;k>=j-d+1;--k) ++fr[k-(j-d+1)+1][cod(a[k])];
                if(j>i+d-1)
                {
                    sum=0;
                    for(k=1;k<=d;++k)
                    {
                        for(jj=mx[k]=0;jj<4;++jj) mx[k]=max(mx[k],fr[k][jj]);
                        sum+=mx[k];
                    }
                    sol[i][j]=min(sol[i][j],j-i+1-sum);
                }
            }
        }
    }
    for(i=1;i<=Q;++i) cout<<sol[xx[i]][yy[i]]<<"\n";
    return 0;
}