#include <bits/stdc++.h>
using namespace std;
const int inf = 1e9 + 7;
const long long INF = 1LL << 60;
const long long mod = 1e9 + 7;
const long double eps = 1e-8;
const long double pi = acos(-1.0);
template <class T>
inline bool chmax(T& a, T b) {
  if (a < b) {
    a = b;
    return 1;
  }
  return 0;
}
template <class T>
inline bool chmin(T& a, T b) {
  if (a > b) {
    a = b;
    return 1;
  }
  return 0;
}
vector<int> Zalgo(const string& s) {
  int n = (int)s.size();
  vector<int> res(n);
  res[0] = n;
  int i = 1, j = 0;
  while (i < n) {
    while (i + j < n && s[j] == s[i + j]) ++j;
    res[i] = j;
    if (j == 0) {
      ++i;
      continue;
    }
    int k = 1;
    while (i + k < n && k + res[k] < j) res[i + k] = res[k], ++k;
    i += k, j -= k;
  }
  return res;
}
void solve() {
  int n, m, q;
  cin >> n >> m >> q;
  string s, t;
  cin >> s >> t;
  string u = t + s;
  auto res = Zalgo(u);
  vector<int> cnt(n + 1, 0);
  for (int i = 0; i < n; i++) {
    cnt[i + 1] = cnt[i] + (res[m + i] >= m ? 1 : 0);
  }
  for (int _ = 0; _ < q; _++) {
    int l, r;
    cin >> l >> r;
    cout << cnt[max(r - m + 1, l - 1)] - cnt[l - 1] << endl;
  }
}
signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  solve();
  return 0;
}
