#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cassert>

using namespace std;

const int MaxN = 605;

int N, NQ, DP[MaxN][MaxN];
char String[MaxN];

inline int Compare(const int s1, const int s2, const int L) {
    int diff = 0;
    for (int i = 0; i < L; ++i)
        diff += (String[s1+i] != String[s2+i]);
    return diff;
}

inline void MakePeriod(const int Start, const int L) {
    int Cost = 0;
    for (int k = 2; Start+k*L-1 < N; ++k) {
        Cost += Compare(Start, Start+(k-1)*L, L);
        DP[Start][k*L] = min(DP[Start][k*L], Cost);
    }
}

void Solve() {
    memset(DP, 0x3f, sizeof(DP));
    for (int i = 0; i < N; ++i) {
        DP[i][1] = 0;
        for (int L = 1; i+L-1 < N; ++L)
            MakePeriod(i, L);
    }
}

void Read() {
    assert(freopen("perb.in", "r", stdin));
    assert(scanf("%d %d\n%s", &N, &NQ, String) == 3);
}

void Print() {
    assert(freopen("perb.out", "w", stdout));
    for (; NQ; --NQ) {
        int X, L; assert(scanf("%d %d", &X, &L) == 2);
        L = L-X+1; --X;
        printf("%d\n", DP[X][L]);
    }
}

int main() {
    Read();
    Solve();
    Print();
    return 0;
}