#include<stdio.h>
int N,M,nr[610][610];
char s[610];
int main(){
	freopen("perb.in","r",stdin);
	freopen("perb.out","w",stdout);
	int i,j,k,x,cnt,y;
	scanf("%d%d",&N,&M);
	fgets(s+1,10,stdin);
	fgets(s+1,N+100,stdin);
	for(i=1;i<=N;++i){
		for(j=1;j<=N;++j)
			nr[i][j]=N+100;
	}
	for(i=1;i<=N;++i){
		nr[i][i]=0;
		for(j=1;j<=(N-i+1)/2;++j){
			cnt=0;
			for(k=i+j,x=i;k<=N;++k,++x){
				if(x==i+j)
					x-=j;
				if(s[x]!=s[k])
					++cnt;
				if(cnt<nr[i][k] && (k-i+1)%j==0)
					nr[i][k]=cnt;
			}
		}
	}
	for(i=0;i<M;++i){
		scanf("%d%d",&x,&y);
		printf("%d\n",nr[x][y]);
	}
	fclose(stdin);
	fclose(stdout);
	return 0;
}