C++ :

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

typedef unsigned long long ull;

const int N=100005;

int n,m;
ull mclock[N],hash1[N],hash2[N];
char ch[N];

bool check(int x,int y,int len)
{
    return (hash1[x+len-1]-hash1[x-1]*mclock[len])==(hash2[y+len-1]-hash2[y-1]*mclock[len]);
}

int get_lcp(int x,int y)
{
    int l=y,r=m;
    while (l<=r)
    {
        int mid=(l+r)/2;
        if (check(x,y,mid-y+1)) l=mid+1;
        else r=mid-1;
    }
    return l-1;
}

int main()
{
    mclock[0]=1;
    for (int i=1;i<=100000;i++) mclock[i]=mclock[i-1]*27;
    int T;scanf("%d",&T);
    while (T--)
    {
        scanf("%s",ch+1);n=strlen(ch+1);
        for (int i=1;i<=n;i++) hash1[i]=hash1[i-1]*27+ch[i]-'A'+1;
        scanf("%s",ch+1);m=strlen(ch+1);
        for (int i=1;i<=m;i++) hash2[i]=hash2[i-1]*27+ch[i]-'A'+1;
        int ans=0;
        for (int i=1;i+m-1<=n;i++)
        {
            int len=1;
            for (int j=1;j<=3;j++)
            {
                len=get_lcp(i+len-1,len)+2;
                if (len>m) break;
            }
            if (len<=m) len=get_lcp(i+len-1,len)+1;
            if (len>m) ans++;
        }
        printf("%d\n",ans);
    }
    return 0;
}