#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1005, MAXM = 1005;
string T, P, tt;
int Next[MAXM], N, M, C;
void MakeNext(int M) {
  int i = 0, j = -1;
  Next[i] = -1;
  while (i < M) {
    if (j == -1 || P[i] == P[j])
      Next[++i] = ++j;
    else
      j = Next[j];
  }
}
int KMP(int pos, int N, int M) {
  int i = pos, j = 0, ans = 0;
  while (i < N) {
    if (T[i] == P[j] || j == -1)
      i++, j++;
    else
      j = Next[j];
    if (j == M) {
      ans++;
      j = Next[j - 1];
      i--;
    }
  }
  return ans;
}
int main() {
  int n, m, q;
  cin >> n >> m >> q;
  cin >> tt >> P;
  int l, r;
  while (q--) {
    cin >> l >> r;
    T = tt.substr(l - 1, r - l + 1);
    N = r - l + 1;
    M = m;
    MakeNext(M);
    printf("%d\n", KMP(0, N, M));
  }
  return 0;
}
