#include <fstream>

using namespace std;

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

const int MAX_LENGTH = 600;
int length, queries, x, y;
int dp[MAX_LENGTH + 2][MAX_LENGTH + 2];
string word;

void precompute() {
    for (int i = 1; i <= length; ++i) {
        for (int j = 1; j <= length; ++j)
            dp[i][j] = j - i;
    }
    
    for (int len = 1; len <= length; ++len) {
        for (int i = 1; i <= length; ++i) {
            int changesNeeded = 0;
            for (int j = i + 1; j <= length; ++j) {
                if (word[(j - i) % len + i - 1] != word[j - 1]) {
                    ++changesNeeded;
                }
                if ((j - i + 1) % len == 0 && j - i + 1 != len) {
                    dp[i][j] = min(dp[i][j], changesNeeded);
                }
            }
        }
    }
}

int main() {
    in >> length >> queries >> word;
    precompute();
    for (int query = 1; query <= queries; ++query) {
        in >> x >> y;
        out << dp[x][y] << "\n";
    }
    
    return 0;
}