//just test
#include<bits/stdc++.h>
#define N 100010
#define LL long long
using namespace std;
char s2[N],s1[N];
LL p[N],H1[N],H2[N],h1[N],h2[N],pp[N];
int a[N],next[N];
const LL P=99959;
const LL MOD=100001651;
const LL MmOD=100001611;
typedef pair<LL,LL> PP;
map<PP,int>s;
int main()
{
    int T,n,m,q,cnt,j,v; LL t; long long k;
    p[0]=1;pp[0]=1;for (int i=1;i<N;i++) p[i]=p[i-1]*P%MOD,pp[i]=pp[i-1]*P%MmOD;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d%d%s%s",&n,&m,&q,s1+1,s2+1);
        next[0]=-1;
        for (int i=1;i<=m;i++)
        {
            int p=next[i-1];
            while (p>=0 && s2[p+1]!=s2[i]) p=next[p];
            next[i]=p+1;
        }
        int qq=m-next[m];if (next[m]*2<m) qq=m;
        s.clear();
        H1[0]=H1[1]=0;h1[0]=h1[1]=0;
        for (int i=1;i<=m;i++) H1[1]=(H1[1]*P+(s1[i]-'a'+1))%MOD,
            h1[1]=(h1[1]*P+(s1[i]-'a'+1))%MmOD;

        for (int i=m+1;i<=n;i++) H1[i-m+1]=((((H1[i-m]-p[m-1]*(s1[i-m]-'a'+1)%MOD)+MOD)%MOD)*P%MOD+(s1[i]-'a'+1))%MOD,
            h1[i-m+1]=((((h1[i-m]-pp[m-1]*(s1[i-m]-'a'+1)%MmOD)+MmOD)%MmOD)*P%MmOD+(s1[i]-'a'+1))%MmOD;

        H2[0]=0;h2[0]=0;for (int i=1;i<=m;i++) H2[i]=(H2[i-1]*P+(s2[i]-'a'+1))%MOD,
                                   h2[i]=(h2[i-1]*P+(s2[i]-'a'+1))%MmOD;
        cnt=0;LL tt;
        for (int i=1;i<=m;i++)
        {
            t=((((H2[m]-H2[i]*p[m-i]%MOD)+MOD)%MOD)*p[i]+H2[i])%MOD;
            tt=((((h2[m]-h2[i]*pp[m-i]%MmOD)+MmOD)%MmOD)*pp[i]+h2[i])%MmOD;
            if (!s[PP(t,tt)])  s[PP(t,tt)]=++cnt,a[cnt]=i;
        }
        while (q--)
        {
            scanf("%d%lld",&j,&k);
            t=H1[j]; tt=h1[j];
            v=s[PP(t,tt)];
            if(!s[PP(t,tt)])puts("0");else printf("%lld\n",(k-a[v]+qq)/qq);
        }
    }
}