1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
#include <iostream>
#include <cstdlib>
#define FOR(i, s, e) for (int i=(s);i<(e);i++)
#define FOE(i, s, e) for (int i=(s);i<=(e);i++)
#define CLR(a, x) memset(a, x, sizeof(a))
#define N 1000005
using namespace std;
int TC, f[N], n, m, x, ret;
char s[N], p[N];
int main(){
    scanf("%d", &TC);
    while (TC--){
        scanf("%s%s", p, s);
        m = strlen(p);
        n = strlen(s);
        x = f[0] = -1;
        FOE(i, 1, m){
            while (x != -1 && p[x] != p[i - 1]) x = f[x];
            f[i] = ++x;
        }
        ret = 0;
        x = 0;
        FOR(i, 0, n){
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX