1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <queue>
#include <deque>
#include <climits>
using namespace std;
void input(int &n, int &m, int &q, string &s, string &t, vector<tuple<int, int, int, int>> &arr) {
  int a, b, c, d;
  cin >> n >> m >> q >> s >> t;
  for (int i = 0; i < q; i++) {
    cin >> a >> b >> c >> d;
    arr.push_back({a - 1, b - 1, c - 1, d - 1});
  }
}
int lcs(string &s, int &s1, int &s2, string &t, int &t1, int &t2) {
  int n = s2 - s1 + 1, m = t2 - t1 + 1;
  vector<vector<int>> dp(n + 1, vector<int>(m + 1));
  for (int i = s1 + 1; i <= s2 + 1; i++) {
    for (int j = t1 + 1; j <= t2 + 1; j++) {
      if (s[i - 1] == t[j - 1]) {
        dp[i - s1][j - t1] = dp[i - 1 - s1][j - 1 - t1] + 1;
      }
      else {
        dp[i - s1][j - t1] = max(dp[i - 1 - s1][j - t1], dp[i - s1][j - 1 - t1]);
      }
    }
  }
  return dp[n][m];
}
void solve(int &n, int &m, int &q, string &s, string &t, vector<tuple<int, int, int, int>> &arr) {
  for (auto& [s1, s2, t1, t2] : arr) {
    cout << lcs(s, s1, s2, t, t1, t2) << "\n";
  }
}
int main() {
  ios_base::sync_with_stdio(0);
  int n, m, q;
  string s, t;
  vector<tuple<int, int, int, int>> arr;
  input(n, m, q, s, t, arr);
  solve(n, m, q, s, t, arr);
  return 0;
}