#ifdef DEBUG
#define _GLIBCXX_DEBUG
#endif
//#pragma GCC optimize("O3")
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
const int maxN = 2 * (int)1e6 + 100;
map < char, int > to[maxN];
int link[maxN];
int len[maxN];
int last = 0;
int sz = 1;
void add_letter(char c) {
    int p = last;
    last = sz++;
    len[last] = len[p] + 1;
    for(; to[p][c] == 0; p = link[p]) {
        to[p][c] = last;
    }
    if (to[p][c] == last) {
        link[last] = 0;
        return;
    }
    int q = to[p][c];
    if (len[q] == len[p] + 1) {
        link[last] = q;
        return;
    }
    int cl = sz++;
    to[cl] = to[q];
    link[cl] = link[q];
    len[cl] = len[p] + 1;
    link[last] = link[q] = cl;
    for (; to[p][c] == q; p = link[p]) {
        to[p][c] = cl;
    }
}
vector<int> prefix_function (string s) {
    int n = (int) s.length();
    vector<int> pi (n);
    for (int i=1; i<n; ++i) {
        int j = pi[i-1];
        while (j > 0 && s[i] != s[j])
            j = pi[j-1];
        if (s[i] == s[j])  ++j;
        pi[i] = j;
    }
    return pi;
}
bool good[maxN];
int n, m, q;
int mx[maxN];
int pref_s[maxN];
ll pref_l[maxN], pref_r[maxN];
void solve() {
    cin >> n >> m >> q;
    string s, t;
    cin >> s >> t;
    auto pr = prefix_function(s);
    for (int i = 0; i <= n; i++) good[i] = false;
    int cur = n;
    for (int i = 0; i <= n; i++) {
        pref_s[i] = 0;
    }
    while (pr[cur - 1] > 0) {
        cur = pr[cur - 1];
        pref_s[n - cur]++;
    }
    for (int i = 1; i <= n; i++) {
        pref_s[i] += pref_s[i - 1];
    }
    s.erase(s.begin());
    s.pop_back();
    for (int i = 0; i < s.size(); i++) {
        add_letter(s[i] - 'a');
    }
    int R = 0;
    int STATE = 0;
    for (int i = 1; i <= m; i++) {
        assert(R + 1 >= i);
        while (R < m && to[STATE].count(t[R] - 'a') && to[STATE][t[R] - 'a'] != 0) {
            STATE = to[STATE][t[R] - 'a'];
            R++;
        }
        mx[i] = R;
        if (R == i - 1) {
            R++;
        }
        else {
            if (len[link[STATE]] + 1 == R - i + 1) {
                STATE = link[STATE];
            }
        }
    }
    for (int i = 1; i <= m; i++) {
        pref_l[i] = pref_l[i - 1] + pref_s[mx[i] - i + 1];
        pref_r[i] = pref_r[i - 1] + pref_s[i];
    }
    while (q--) {
        int l, r;
        cin >> l >> r;
        int R = r + 1;
        int L = l - 1;
        while (R - L > 1) {
            int mid = (L + R) / 2;
            if (mx[mid] >= r) R = mid;
            else L = mid;
        }
        ll ans = pref_l[L] - pref_l[l - 1] + pref_r[r - R + 1];
        cout << ans << '\n';
    }


    for (int i = 0; i < sz; i++) {
        to[i].clear();
    }
    sz = 1;
    last = 0;
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
#ifdef DEBUG
    freopen("input.txt", "r", stdin);
#endif
    int tst;
    cin >> tst;
    while (tst--) {
        solve();
    }
    return 0;
}