法国作家乔治·佩雷克(Georges Perec，1936-1982)曾经写过一本书，《敏感字母》（La disparition），全篇没有一个字母‘e’。他是乌力波小组（Oulipo Group）的一员。下面是他书中的一段话：

Tout avait Pair normal, mais tout s’affirmait faux. Tout avait Fair normal, d’abord, puis surgissait l’inhumain, l’affolant. Il aurait voulu savoir où s’articulait l’association qui l’unissait au roman : stir son tapis, assaillant à tout instant son imagination, l’intuition d’un tabou, la vision d’un mal obscur, d’un quoi vacant, d’un non-dit : la vision, l’avision d’un oubli commandant tout, où s’abolissait la raison : tout avait l’air normal mais…

佩雷克很可能在下面的比赛中得到高分（当然，也有可能是低分）。在这个比赛中，人们被要求针对一个主题写出甚至是意味深长的文章，并且让一个给定的“单词”出现次数尽量少。我们的任务是给评委会编写一个程序来数单词出现了几次，用以得出参赛者最终的排名。参赛者经常会写一长串废话，例如500000个连续的‘T’。并且他们不用空格。

因此我们想要尽快找到一个单词出现的频数，即一个给定的字符串在文章中出现了几次。更加正式地，给出字母表{'A','B','C',...,'Z'}和两个仅有字母表中字母组成的有限字符串：单词W和文章T，找到W在T中出现的次数。这里“出现”意味着W中所有的连续字符都必须对应T中的连续字符。T中出现的两个W可能会部分重叠。 输入包含多组数据。

输入文件的第一行有一个整数，代表数据组数。接下来是这些数据，以如下格式给出：

第一行是单词W，一个由{'A','B','C',...,'Z'}中字母组成的字符串，保证1<=|W|<=10000（|W|代表字符串W的长度）

第二行是文章T，一个由{'A','B','C',...,'Z'}中字母组成的字符串，保证|W|<=|T|<=1000000。

对每组数据输出一行一个整数，即W在T中出现的次数。

#include<bits/stdc++.h>
using namespace std;
#define int long long 
char s[1000010],s1[1000010];
int n,ans=0,qhs1,qhs2;
int mod1=805306457,mod2=998244353;
int p1[1000010],p2[1000010],hs1[1000010],hs2[1000010];
int wen1(int l,int r){return((hs1[r]-hs1[l-1]*p1[r-l+1])%mod1+mod1)%mod1;}
int wen2(int l,int r){return((hs2[r]-hs2[l-1]*p2[r-l+1])%mod2+mod2)%mod2;}
signed main()
{
    scanf("%lld",&n);
    p1[1]=p2[1]=13331;
    for(int i=2;i<=1000000;++i)
    {
        p1[i]=(p1[i]*p1[i-1])%mod1;
        p2[i]=(p2[i]*p2[i-1])%mod2;
    }
    for(int j=1;j<=n;++j)
    {
        ans=0;
        scanf("%s",s);
        scanf("%s",s1);
        int ss=strlen(s),ss1=strlen(s1);
        hs1[1]=hs2[1]=qhs1=qhs2=0;
        for(int i=1;i<=ss1;++i)
            hs1[i]=(hs1[i-1]*p1[1]+s1[i-1])%mod1,
            hs2[i]=(hs2[i-1]*p2[1]+s1[i-1])%mod2;
        for(int i=0;i<ss;++i)
            qhs1=(qhs1*p1[1]+s[i])%mod1,qhs2=(qhs2*p2[1]+s[i])%mod2;
        for(int i=ss;i<=ss1;++i)if(wen1(i-ss+1,i)==qhs1&&wen2(i-ss+1,i)==qhs2)++ans;
        cout<<ans<<'\n';
    }
}