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