#include <bits/stdc++.h>
using namespace std;
long long mod = 1000000007;
long long z[3000019], arr[3000019], pre[3000019];
void fnc(string s) {
  memset(z, 0, sizeof(z));
  long long l = 0, r = 0;
  long long n = s.size();
  for (long long i = 1; i <= n; i++) {
    if (i <= r) z[i] = min(r - i + 1, z[i - l]);
    while (i + z[i] <= n && s[z[i]] == s[i + z[i]]) z[i]++;
    if (i + z[i] - 1 > r) {
      l = i;
      r = i + z[i] - 1;
    }
  }
  z[0] = n;
  return;
}
signed main() {
  std::ios::sync_with_stdio(false);
  long long n, m, q, i, l, r;
  string s, t, str;
  cin >> n >> m >> q;
  cin >> s >> t;
  str = t + "$" + s;
  fnc(str);
  for (i = m + 1; i <= n + m; i++) arr[i - m] = (z[i] == m);
  for (i = 1; i <= n; i++) pre[i] = arr[i] + pre[i - 1];
  while (q--) {
    cin >> l >> r;
    if (r - l + 1 < m) {
      cout << 0 << endl;
      continue;
    }
    cout << pre[r - m + 1] - pre[l - 1] << endl;
  }
  return 0;
}
