#include <bits/stdc++.h>

#define N_MAX 602

using namespace std;

int n, m;

string s;

int ans[N_MAX][N_MAX];

int cost[N_MAX];

int main()
{
    ifstream fin ("perb.in");
    ofstream fout ("perb.out");
    fin >> n >> m;
    fin >> s;
    s = " " + s;
    for(int i = 1; i <= n; i++)
    {
        int prefLg = n - i + 1;
        memset(cost, 0, sizeof(cost));
        for(int j = i; j <= n; j++)
        {
            int lg = j - i + 1;
            int mi = n;
            for(int k = 1; k * 2 <= prefLg; k++)
            {
                if(j - k >= i)
                    cost[k] += (s[j - k] != s[j]);
                if(lg % k == 0 && k < lg)
                    mi = min(mi, cost[k]);
            }
            ans[i][j] = mi;
        }
    }
    while(m--)
    {
        int l, r;
        fin >> l >> r;
        fout << ans[l][r] << "\n";
    }
    return 0;
}