#include<bits/stdc++.h>
#define mp make_pair
#define PII pair<int,int>
#define fi first
#define se second
using namespace std;

ifstream fin("perb.in");
ofstream fout("perb.out");

const int NMAX=605;

int n,m,dp[NMAX][NMAX],fr[NMAX][5];
char s[NMAX];

int main()
{
    int i,j,l,x,y,aux,sum,cnt;
    fin>>n>>m;
    fin>>(s+1);
    for (i=1;i<=n;i++)
        for (j=1;j<=n;j++)
            dp[i][j]=1<<30;
    for (i=1;i<=n;i++)//aleg divizorul
        for (j=i*2;j<=n;j+=i)//aleg lungimea care e multiplu
            {
                sum=0;
                for (l=0;l<i;l++) fr[l][1]=fr[l][2]=fr[l][3]=fr[l][4]=0;
                cnt=0;
                for (l=1;l<=n;l++)
                    {
                        cnt++;
                        if (cnt>=i) cnt-=i;
                        aux=cnt;sum-=max(fr[aux][1],max(fr[aux][2],max(fr[aux][3],fr[aux][4])));
                        if (s[l]=='A') fr[aux][1]++;
                        if (s[l]=='C') fr[aux][2]++;
                        if (s[l]=='G') fr[aux][3]++;
                        if (s[l]=='T') fr[aux][4]++;
                        if (l>j)
                            {
                                if (s[l-j]=='A') fr[aux][1]--;
                                if (s[l-j]=='C') fr[aux][2]--;
                                if (s[l-j]=='G') fr[aux][3]--;
                                if (s[l-j]=='T') fr[aux][4]--;
                            }
                        sum+=max(fr[aux][1],max(fr[aux][2],max(fr[aux][3],fr[aux][4])));
                        if (l>=j) dp[l-j+1][l]=min(dp[l-j+1][l],j-sum);
                    }
            }
    for (i=1;i<=m;i++)
        {
            fin>>x>>y;
            fout<<dp[x][y]<<"\n";
        }
    return 0;
}