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

const int NMAX=605;

int n,m,sum[NMAX][NMAX],diviz[NMAX][NMAX],len[NMAX];
char s[NMAX];

void Afla()
{
    int i,j,sq;
    for (i=1;i<=n;i++)
        {
            sq=sqrt(i);
            diviz[i][++len[i]]=1;
            for (j=2;j<=sq;j++)
                if (i%j==0)
                    {
                        diviz[i][++len[i]]=j;
                        diviz[i][++len[i]]=i/j;
                    }
            if (sq*sq==i) len[i]--;
        }
}

int main()
{
    int i,j,mn,dif,aux,x,y;
    freopen("perb.in","r",stdin);
    freopen("perb.out","w",stdout);
    cin.sync_with_stdio(false);
    cin>>n>>m;
    cin>>(s+1);
    for (j=1;j<n;j++)//lungimea
        for (i=1;i<=(n-j);i++)
            if (s[i]!=s[i+j])
                sum[j][i]=sum[j][i-1]+1;
            else sum[j][i]=sum[j][i-1];
    Afla();
    for (i=1;i<=m;i++)
        {
            cin>>x>>y;mn=1<<30;
            dif=y-x+1;
            for (j=1;j<=len[dif];j++)//merg pe divizori,numai ei pot fi lungimi de perioada
                {
                    aux=diviz[dif][j];
                    mn=min(mn,sum[aux][y-aux]-sum[aux][x-1]);
                }
            cout<<mn<<"\n";
        }
    return 0;
}