#include <bits/stdc++.h>
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second
#define F(i, x, y) for (int i = (x); i <= (y); i++)
#define R(i, x, y) for (int i = (x); i >= (y); i--)
#define FIO(FILE) freopen(FILE".in", "r", stdin), freopen(FILE".out", "w", stdout)

using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
bool Mbe;

const int N = 5e5 + 5;
const int M = 20;

int n, m, ans[N];
char s[N];

struct SA {
	
	int len;
	int sa[N], id[N], rk[N], ct[N], ht[N], f[N][M];
	
	void rst() {
		memset(ct, 0, sizeof(int) * (len + 1));
		F (i, 1, n) {
			ct[rk[i]]++;
		}
		F (i, 1, len) {
			ct[i] += ct[i - 1];
		}
		R (i, n, 1) {
			sa[ct[rk[id[i]]]--] = id[i];
		}
	}
	
	void init() {
		len = 30;
		F (i, 1, n) {
			id[i] = i;
			rk[i] = s[i] - 'a' + 1; 
		}
		rst();
		for (int w = 1, p = 0; w <= n && p != n; w <<= 1, len = p) {
			p = 0;
			F (i, n - w + 1, n) {
				id[++p] = i;
			}
			F (i, 1, n) {
				if (sa[i] > w) {
					id[++p] = sa[i] - w;
				}
			}
			rst();
			swap(rk, id);
			rk[sa[1]] = p = 1;
			F (i, 2, n) {
				rk[sa[i]] = (id[sa[i]] == id[sa[i - 1]] && id[sa[i] + w] == id[sa[i - 1] + w]) ? p : ++p;
			}
		}
		int j = 0;
		F (i, 1, n) {
			if (j) {
				j--;
			}
			while (s[i + j] == s[sa[rk[i] - 1] + j]) {
				j++;
			}
			ht[rk[i]] = j;
		}
		F (i, 1, n) {
			f[i][0] = ht[i];
		}
		F (j, 1, __lg(n)) {
			F (i, 1, n - (1 << j) + 1) {
				f[i][j] = min(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
			}
		}
	}
	
	int lcp(int l, int r) {
		if (l == r) {
			return n - l + 1;
		}
		int _l = rk[l], _r = rk[r];
		l = min(_l, _r) + 1, r = max(_l, _r);
		int len = __lg(r - l + 1);
		return min(f[l][len], f[r - (1 << len) + 1][len]);
	}
	
} A, B;

struct Q {
	
	int x, o, i;
	
	Q () { }
	Q (int _x, int _o, int _i) : x(_x), o(_o), i(_i) { }
	
};

struct BIT {
	
	int t[N];
	
	int lb(int x) {
		return x & -x;
	}
	
	void u(int x, int y, int o) {
		for (int i = x; i && i <= n; i += o * lb(i)) {
			t[i] += y;
		}
	}
	
	int q(int x, int o) {
		int res = 0;
		for (int i = x; i && i <= n; i += o * lb(i)) {
			res += t[i];
		}
		return res;
	}
	
} T1, T2;

vector<Q> up[N];
vector<Q> qa[N], qb[N];

void solve() {
	cin >> n >> n >> m >> (s + 1);
	A.init(), reverse(s + 1, s + n + 1);
	B.init();
	F (i, 1, m) {
		int l, r;
		cin >> l >> r;
		qa[l + 1].eb(Q(A.rk[l], 1, i));
		qa[l + r + 1].eb(Q(A.rk[l], -1, i));
		qb[l].eb(Q(r, 1, i));
	}
	R (i, n, 1) {
		T1.u(A.rk[i], 1, -1);
		for (Q j : qa[i]) {
			int x = j.x, o = j.o, id = j.i;
			ans[id] += o * T1.q(x, 1);
		}
	}
	F (d, 1, n >> 1) {
		for (int i = d, j = 2 * d; j <= n; i += d, j += d) {
			int lcp = min(A.lcp(i, j), d);
			int lcs = min(B.lcp(n - i + 2, n - j + 2), d - 1);
			if (lcp + lcs >= d) {
				int l = i - lcs, r = i + lcp - d;
				if (A.rk[l] >= A.rk[l + d]) {
					continue;
				}
				up[l].eb(Q(d, 1, 0));
				up[r + 1].eb(Q(d, -1, 0));
			}
		}
	} 
	F (i, 1, n) {
		for (Q j : up[i]) {
			int x = j.x, o = j.o;
			// assert(x <= n && x >= 1);
			T2.u(x, o, 1);
		}
		for (Q j : qb[i]) {
			int x = j.x, id = j.i;
			// assert(x <= n && x >= 1);
			ans[id] -= T2.q(x, -1);
		}
	}
	F (i, 1, m) {
		cout << ans[i] << '\n';
	}
}

bool Med;
int main() {
	// FIO("");
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cerr << (&Mbe - &Med) / 1048576.0 << " MB\n";
	int T = 1;
	// cin >> T;
	while (T--) solve();
	cerr << (int)(1e3 * clock() / CLOCKS_PER_SEC) << " ms\n";
	return 0;
}