//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);
        }
    }
}

answer.code: In function ‘int main()’:
answer.code:22:9: error: reference to ‘next’ is ambiguous
   22 |         next[0]=-1;
      |         ^~~~
In file included from /usr/include/c++/13/bits/stl_algobase.h:66,
                 from /usr/include/c++/13/algorithm:60,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:51,
                 from answer.code:2:
/usr/include/c++/13/bits/stl_iterator_base_funcs.h:232:5: note: candidates are: ‘template<class _InputIterator> constexpr _InputIterator std::next(_InputIterator, typename iterator_traits<_Iter>::difference_type)’
  232 |     next(_InputIterator __x, typename
      |     ^~~~
answer.code:8:10: note:                 ‘int next [100010]’
    8 | int a[N],next[N];
      |          ^~~~
answer.code:25:19: error: reference to ‘next’ is ambiguous
   25 |             int p=next[i-1];
      |                   ^~~~
/usr/include/c++/13/bits/stl_iterator_base_funcs.h:232:5: note: candidates are: ‘template<class _InputIterator> constexpr _InputIterator std::next(_InputIterator, typename iterator_traits<_Iter>::difference_type)’
  232 |     next(_InputIterator __x, typename
      |     ^~~~
answer.code:8:10: note:                 ‘int next [100010]’
    8 | int a[N],next[N];
      |          ^~~~
answer.code:26:46: error: reference to ‘next’ is ambiguous
   26 |             while (p>=0 && s2[p+1]!=s2[i]) p=next[p];
      |                                              ^~~~
/usr/include/c++/13/bits/stl_iterator_base_funcs.h:232:5: note: candidates are: ‘template<class _InputIterator> constexpr _InputIterator std::next(_InputIterator, typename iterator_traits<_Iter>::difference_type)’
  232 |     next(_InputIterator __x, typename
      |     ^~~~
answer.code:8:10: note:                 ‘int next [100010]’
    8 | int a[N],next[N];
      |          ^~~~
answer.code:27:13: error: reference to ‘next’ is ambiguous
   27 |             next[i]=p+1;
      |             ^~~~
/usr/include/c++/13/bits/stl_iterator_base_funcs.h:232:5: note: candidates are: ‘template<class _InputIterator> constexpr _InputIterator std::next(_InputIterator, typename iterator_traits<_Iter>::difference_type)’
  232 |     next(_InputIterator __x, typename
      |     ^~~~
answer.code:8:10: note:                 ‘int next [100010]’
    8 | int a[N],next[N];
      |          ^~~~
answer.code:29:18: error: reference to ‘next’ is ambiguous
   29 |         int qq=m-next[m];if (next[m]*2<m) qq=m;
      |                  ^~~~
/usr/include/c++/13/bits/stl_iterator_base_funcs.h:232:5: note: candidates are: ‘template<class _InputIterator> constexpr _InputIterator std::next(_InputIterator, typename iterator_traits<_Iter>::difference_type)’
  232 |     next(_InputIterator __x, typename
      |     ^~~~
answer.code:8:10: note:                 ‘int next [100010]’
    8 | int a[N],next[N];
      |          ^~~~
answer.code:29:30: error: reference to ‘next’ is ambiguous
   29 |         int qq=m-next[m];if (next[m]*2<m) qq=m;
      |                              ^~~~
/usr/include/c++/13/bits/stl_iterator_base_funcs.h:232:5: note: candidates are: ‘template<class _InputIterator> constexpr _InputIterator std::next(_InputIterator, typename iterator_traits<_Iter>::difference_type)’
  232 |     next(_InputIterator __x, typename
      |     ^~~~
answer.code:8:10: note:                 ‘int next [100010]’
    8 | int a[N],next[N];
      |          ^~~~
answer.code:18:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   18 |     scanf("%d",&T);
      |     ~~~~~^~~~~~~~~
answer.code:21:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   21 |         scanf("%d%d%d%s%s",&n,&m,&q,s1+1,s2+1);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
answer.code:49:18: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   49 |             scanf("%d%lld",&j,&k);
      |             ~~~~~^~~~~~~~~~~~~~~~