JUMPin' JUMP UP!!!

Tired of solving mathematical equations, DreamGrid starts to solve equations related to strings: for two strings  and  with the same length consisting of lowercase English letters, calculate , which is defined as the number of nonempty strings  consisting of lowercase English letters such that  and the length of  does not exceed .

DreamGrid has two strings  and . He would like to ask several questions about the value of , where  is the substring of  starting from  with length  and  is a given number.

Input

There are multiple test cases. The first line of input contains an integer , indicating the number of test cases. For each test case:

The first line contains three integers  and  and  () -- the length of , the length of  and the number of questions.

The second line contains  lowercase English letters denoting the string . The third line contains  lowercase English letters denoting the string .

Each of the next  lines contains two integers  and  () denoting the -th question.

It is guaranteed that neither the sum of all  nor the sum of all  exceeds .

Output

For each question, output an integer denoting the answer.

Sample Input

1
4 2 3
abcd
ba
1 2
2 2
3 2

Sample Output

1
0
0

题目大意：

两个字符串x，y，和另一个字符串z，若xz=zy，则称x，y在z下匹配。现在已知两个字符串x，y，求多少个z能使之匹配（|z|<LIMIT）.

题解：


Z的长度为2,2+4,2+4+4，都可以，所以求出断点后，加上某个数的倍数都可以。


暴力短串的断点，将m种情况用hash存下来。

（每种情况都有无数种方案c，c+k，c+2k，C+3k……）

对于每个询问，判断hash中是否存在，再输出可行的方案数目。（有长度限制的缘故）。

字典序hash会被卡掉，所以要用2种模数来判断


代码：

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