#include <fstream>
#include <cstring>
#define N 601
using namespace std;
ifstream f("perb.in");
ofstream g("perb.out");
int d[N][N],n,m,i,j,l,c,fr[51],viz[51],x,y,sol,per;
char S[N];
int main()
{   f>>n>>m;
    f>>(S+1);
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
            d[i][j]=N;
    for(i=1;i<=n;i++)
        d[i][i]=0;
    for(l=1;l<=n;l++){
        for(i=1;i<=n-l+1;i++){
            per=1;
            sol=0;
            for(j=i+l;j<=n;j++){
                if(S[j-per*l]!=S[j])
                    sol++;
                if((j-i+1)%l==0){
                    d[i][j]=min(d[i][j],sol);
                    per++;
                }
            }
        }
    }
    for(i=1;i<=m;i++){
        f>>x>>y;
        g<<d[x][y]<<'\n';
    }
    return 0;
}