#include <bits/stdc++.h>   using namespace std;   struct Node {     int d;     struct Node *left, *right;   };   int p[1000][1000] = {0};   string s, t;   void dp(int i, int j) {     if (j - i + 1 == t.size()) {       int f = 1;       for (int z = 0; z < t.size(); z++) {         if (s[i + z] != t[z]) {           f = 0;           break;         }       }       if (f == 1) p[i][j] = 1;     } else if (j - i + 1 < t.size())       return;     else if (j - i + 1 > t.size()) {       int maxm = 0, l = t.size();       for (int x = i; x <= j - l + 1; x++) {         if (p[x][x + l - 1] > 0) p[i][j]++;       }     }     return;   }   int main() {     int n, m, q;     cin >> n >> m >> q;     int a[q][2];     getchar();     cin >> s;     getchar();     cin >> t;     for (int i = 0; i <= q - 1; i++) {       cin >> a[i][0] >> a[i][1];     }     int l = t.size();     for (int si = l; si <= n; si++) {       for (int j = 0; j <= n - si; j++) dp(j, j + si - 1);     }     for (int i = 0; i <= q - 1; i++) cout << p[a[i][0] - 1][a[i][1] - 1] <<   n ;   }   