#include <bits/stdc++.h>
 
using namespace std;
 
const int N = 1<<20;
 
int n,m;
char a[N];
 
bool check(int x, int y, int z, int w) {
	int i=x,j=z;
	while(i<=y) {
		if(a[i]!=a[j]) return false;
		++i;
		++j;
	}
	return true;
}
 
int main() {
	int i,cnt,l,r;
 
	scanf("%d %d", &n, &m);
	scanf("%s", a+1);
	while(m--) {
		scanf("%d %d", &l, &r);
		cnt=1;
		for(i=r+1;i+(r-l+1)-1<=n;i+=(r-l+1)) {
			if(check(l,r,i,i+(r-l+1)-1)) ++cnt;
			else break;
		}
		printf("%d\n", cnt);
	}
 
	return 0;
}

I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+Cgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKY29uc3QgaW50IE4gPSAxPDwyMDsKCmludCBuLG07CmNoYXIgYVtOXTsKCmJvb2wgY2hlY2soaW50IHgsIGludCB5LCBpbnQgeiwgaW50IHcpIHsKCWludCBpPXgsaj16OwoJd2hpbGUoaTw9eSkgewoJCWlmKGFbaV0hPWFbal0pIHJldHVybiBmYWxzZTsKCQkrK2k7CgkJKytqOwoJfQoJcmV0dXJuIHRydWU7Cn0KCmludCBtYWluKCkgewoJaW50IGksY250LGwscjsKICAgIAoJc2NhbmYoIiVkICVkIiwgJm4sICZtKTsKCXNjYW5mKCIlcyIsIGErMSk7Cgl3aGlsZShtLS0pIHsKCQlzY2FuZigiJWQgJWQiLCAmbCwgJnIpOwoJCWNudD0xOwoJCWZvcihpPXIrMTtpKyhyLWwrMSktMTw9bjtpKz0oci1sKzEpKSB7CgkJCWlmKGNoZWNrKGwscixpLGkrKHItbCsxKS0xKSkgKytjbnQ7CgkJCWVsc2UgYnJlYWs7CgkJfQoJCXByaW50ZigiJWRcbiIsIGNudCk7Cgl9CgkKCXJldHVybiAwOwp9