#include <bits/stdc++.h>
#define rep(i,j,k) for(int i=(j);i<=(k);i++)
#define per(i,j,k) for(int i=(j);i>=(k);i--)
#define uint unsigned int
#define ll long long
#define ull unsigned long long
#define db double
#define ldb long double
#define pii pair<int,int>
#define pll pair<ll,ll>
#define mkp make_pair
#define eb emplace_back
#define SZ(S) (int)S.size()
//#define mod 998244353
//#define mod 1000000007
#define inf 0x3f3f3f3f
#define linf 0x3f3f3f3f3f3f3f3f
using namespace std;

template <class T>
void chkmax(T &x,T y){
	if(x < y) x = y;
}

template <class T>
void chkmin(T &x,T y){
	if(x > y) x = y;
}

inline int popcnt(int x){
	return __builtin_popcount(x);
}

inline int ctz(int x){
	return __builtin_ctz(x);
}


/*ll power(ll p,int k = mod - 2){
	ll ans = 1;
	while(k){
		if(k % 2 == 1) ans = ans * p % mod;
		p = p * p % mod;
		k /= 2;	
	}
	return ans;
}*/
int TEST,n,m,q;
char s[100005],t[100005],str[200005];

int z[200005];
void calc(int L){
	int l = 1,r = 0;
	rep(i,2,L){
		if(i <= r) z[i] = min(r - i + 1,z[i - l + 1]);
		else z[i] = 0;
		while(i + z[i] <= L && str[1 + z[i]] == str[i + z[i]]) z[i]++;
		if(i + z[i] - 1 > r){
			l = i;
			r = i + z[i] - 1;
		}
	}
}

int lcp[100005],lcs[100005],sum[100005],ans[100005];
int getsum(int l,int r){
	if(l > r) return 0;
	return sum[r] - sum[l - 1];
}

void solve(){
	scanf("%d%d%d",&n,&m,&q);
	scanf("%s",s + 1);
	scanf("%s",t + 1);
	rep(i,1,m) str[i] = t[i];
	calc(m);
	int per = m;
	rep(i,2,m) if(z[i] == m - i + 1 && m % (i - 1) == 0) chkmin(per,i - 1);

	int sz = 0;
	rep(i,1,per) str[++sz] = t[i];
	rep(i,1,n) str[++sz] = s[i];
	calc(sz);
	rep(i,1,n) lcp[i] = min(per,z[per + i]);

	sz = 0;
	per(i,per,1) str[++sz] = t[i];
	per(i,n,1) str[++sz] = s[i];
	calc(sz);
	per(i,n,1) lcs[i] = min(per,z[per + n - i + 1]);

	rep(i,per + 1,m) sum[i] = sum[i - 1] + (s[i] != s[i - per]);
	fill(ans,ans + n + 1,-1);
	rep(p,1,n){
		int pl = p - min(per - 1,lcs[p - 1]),pr = p + lcp[p] - per;
//		printf("%d->[%d,%d]\n",p,pl,pr);
		rep(k,pl,pr){
			assert(ans[k] == -1);
			ans[k] = p - k;
		}
	}
	rep(i,1,q){
		int pos;
		ll len;
		scanf("%d%lld",&pos,&len);
		if(getsum(pos + per,pos + m - 1)){
			printf("0\n");
			continue;
		}
		if(ans[pos] == -1){
			printf("0\n");
			continue;
		}
		int dd = ans[pos];
		if(dd) dd = per - dd;
/*		rep(ss,0,m - 1) printf("%c",s[pos + ss]);
		printf("\n");
		printf("dd=%d\n",dd);*/
		len -= dd;
		if(len < 0){
			printf("0\n");
		}else{
			printf("%lld\n",len / per + (dd > 0));
		}
	}
}

int main(){
#ifdef cxy
	freopen("test.in","r",stdin);
#endif
	scanf("%d",&TEST);
	while(TEST--) solve();
	return 0;
}