#include <fstream>

using namespace std;

ifstream f ("perb.in");
ofstream g ("perb.out");

int n, m;

char s[605];

int sol[605][605];

int main()
{
    f >> n >> m;
    f >> (s+1);

    for (int i=1; i<=n; ++i)
        for (int j=1; j<=n; ++j)
            sol[i][j] = n;

    for (int d=1; d<=n; ++d)
    {
        for (int i=1; i<=n; ++i)
        {
            int nr=0;
            int ans=0;
            for (int j=i; j<=n; ++j)
            {
                if (s[j] != s[i+nr]) ans++;
                if ((j - i + 1)%d==0 && (j-i+1) != d) sol[i][j] = min(sol[i][j], ans);
                nr++;
                if (nr == d) nr=0;
            }
        }
    }

    for (int i=1; i<=m; ++i)
    {
        int st, dr;
        f >> st >> dr;

        g << sol[st][dr] << '\n';
    }
    return 0;
}