#include <cstdio>
#include <cstring>
#include <algorithm>
#define maxN 602
using namespace std;
int n, m, l, k, x, y, i, j, dp[maxN][maxN], a[maxN][maxN];
char s[maxN];
void read()
{
    freopen("perb.in", "r", stdin);
    scanf("%d %d\n", &n, &m);
    gets(s + 1);
}
void solve()
{
    for (i = 1; i <= n; ++ i)
        for (j = i; j <= n; ++ j)
            a[i][j] = j - i + 1;
    for (l = 1; l <= n; ++ l)
    {
        memset(dp, 0, sizeof(dp));
        for (x = n; x >= 1; -- x)
            for (y = x; y <= n; ++ y)
                if (x + l <= y)
        {
            dp[x][y] = dp[x + 1][y] + (s[x] != s[x + l]);
            if ((y - x + 1) % l == 0)
                a[x][y] = min(a[x][y], dp[x][y]);
        }
    }
}
void write()
{
    freopen("perb.out", "w", stdout);
    while (m --)
    {
        scanf("%d %d", &x, &y);
        printf("%d\n", a[x][y]);
    }
}
int main()
{
    read();
    solve();
    write();
    return 0;
}