/*HDU 6068 - Classic Quotation [ KMP,DP ]  |  2017 Multi-University Training Contest 4题意：	给出两个字符串 S[N], T[M], k个询问	每个询问给出 L,R 		对所有 1<=i<=L , r<=j<=N ，		S串拿掉[i+1,j-1]的子串后，剩下两个子串拼在一起的子串中 T 串的数目求和	限制 N,k <= 5e4, M <= 100分析：	pre[i] 代表 前缀i匹配的T的数目	num[i][j] = 1 代表 前缀i，失配位置为 j	将 pre[i], num[i][j] 求前缀和	suf[i][j] 代表 后缀i,从T[j]开始匹配上的T的数目	ans = pre[L] * (n-R+1) + ∑_[1<=i<=m] num[l][i] * suf[R][i]	所以对于每个询问可 O(m) 时间内求出	pre[i], num[i][j] 可 KMP 过程中求出		设 match[j][k] = 1 代表 T 匹配到 j 时，主串字符为 k 时，新增答案	nxt2[j][k] 代表 T 匹配到 j 时，主串字符为 k 时，下一个失配位置	suf[i][j] = match[j][S[i]] + suf[i+1][nxt[j][S[i]]]	所以 suf可以从后往前 DP	而 match[j][k] 和 nxt2[j][k] 可以 O(m*26) 的时间内暴力求 */#include 
     
      using namespace std;const int N = 50005;const int M = 105;char y[N], x[M];int nxt[N];void GetNxt(char x[], int m){    int i = 0, j = -1;    nxt[0] = -1;    while (i < m)    {        while (j != -1 && x[i] != x[j]) j = nxt[j];        nxt[++i] = ++j;    }}int t, n, m, q;int pre[N];int num[N][M];int suf[N][M];int nxt2[M][256];bool match[M][256];void init(){    memset(pre, 0, sizeof(pre));    memset(num, 0, sizeof(num));    memset(match, 0, sizeof(match));    memset(suf, 0, sizeof(suf));    int j = 0;    for (int i = 0; i < n; i++)    {        while (j != -1 && y[i] != x[j]) j = nxt[j];        j++;        if (j == m) pre[i]++, j = nxt[j];        num[i][j]++;        pre[i] += pre[i-1];    }    for (int i = 1; i < n; i++)    {        pre[i] += pre[i-1];        for (int j = 0; j < m; j++)            num[i][j] += num[i-1][j];    }    for (int i = 0; i < m; i++)        for (int j = 'a'; j <= 'z'; j++)        {            int k = i;            while (k != -1 && x[k] != j) k = nxt[k];            k++;            if (k == m) match[i][j] = 1, k = nxt[k];            nxt2[i][j] = k;        }    for (int i = n-1; i >= 0; i--)        for (int j = 0; j < m; j++)            suf[i][j] = match[j][y[i]] + suf[i+1][nxt2[j][y[i]]];    for (int i = n-1; i >= 0; i--)        for (int j = 0; j < m; j++)            suf[i][j] += suf[i+1][j];}int main(){    scanf("%d", &t);    while (t--)    {        scanf("%d%d%d", &n, &m, &q);        scanf("%s%s", y, x);        GetNxt(x, m);        init();        while (q--)        {            int l, r; scanf("%d%d", &l, &r);            l--, r--;            long long ans = 1LL * (n-r)*pre[l];            for (int i = 0; i < m; i++)                ans += 1LL * num[l][i] * suf[r][i];            printf("%lld\n", ans);        }    }}