#include<cstdio>
#include<algorithm>
using namespace std;
char ch[605];
int dp[605][605],f[605][10];
int maxim(int a,int b,int c,int d){
int maxi=a;
if (b>maxi)
maxi=b;
if (c>maxi)
maxi=c;
if (d>maxi)
maxi=d;
return maxi;}
int main(){
freopen("perb.in","r",stdin);
freopen("perb.out","w",stdout);
int n,m,i,j,k,l,cnt,r,x,y;
scanf("%d%d%s",&n,&m,ch+1);
for(i=1;i<=n;i++)
if (ch[i]=='A')
ch[i]=0;
else
if (ch[i]=='C')
ch[i]=1;
else
if (ch[i]=='G')
ch[i]=2;
else
ch[i]=3;
for(i=1;i<=n;i++)
for(j=i+1;j<=n;j++)
dp[i][j]=j-i+1;
for(i=1;i<=n;i++)
for(l=1;i+2*l-1<=n;l++){
cnt=1;
for(j=0;j<l;j++)
f[j][0]=f[j][1]=f[j][2]=f[j][3]=0,++f[j][ch[i+j]];
for(j=i+2*l-1;j<=n;j=j+l){
r=0;
++cnt;
for(k=0;k<l;k++)
++f[k][ch[j-l+k+1]],r+=cnt-maxim(f[k][0],f[k][1],f[k][2],f[k][3]);
dp[i][j]=min(r,dp[i][j]);}}
for(i=1;i<=m;i++)
scanf("%d%d",&x,&y),printf("%d\n",dp[x][y]);
return 0;}