#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 1e5 + 10;
const int MOD = 1e9 + 7;
const int p = 31;

int n;
char R[N], S[N];
int m, hr[N], hs[N], pw[N];

void clear() {
    memset(R, 0, sizeof R);
    memset(S, 0, sizeof S);
    memset(hr, 0, sizeof hr);
    memset(hs, 0, sizeof hs);
    memset(pw, 0, sizeof pw);
}

bool match(int lr, int rr, int ls) {
    int len = rr - lr + 1;
    int r_hash = (hr[rr] - (ll)hr[lr - 1] * pw[len] % MOD + MOD) % MOD;
    int s_hash = (hs[ls + len - 1] - (ll)hs[ls - 1] * pw[len] % MOD + MOD) % MOD;
    return r_hash == s_hash;
}

int find(int lr, int rr, int ls) {
    //R[lr + f - 1] != S[ls + f - 1]
    int len = rr - lr + 1;
    int l = 1, r = len;
    while (l <= r) {
        int mid = (l + r) >> 1;
        if (match(lr, lr + mid - 1, ls)) l = mid + 1;
        else r = mid - 1;
    }
    return l;
}

void solve() {
    if (n < m) {cout << 0; return ;}
    pw[0] = 1;
    for (int i = 1; i <= n; ++i) {
        hr[i] = ((ll) hr[i - 1] * p + R[i] - 'a') % MOD;
        pw[i] = (ll)pw[i - 1] * p % MOD;
    }
    for (int i = 1; i <= m; ++i) {
        hs[i] = ((ll)hs[i - 1] * p + S[i] - 'a') % MOD;
    }

    int ans = 0;
    for (int i = 1; i + m - 1 <= n; ++i) {
        if (match(i, i + m - 1, 1)) {
            ++ ans;
            continue;
        }
        int f = find(i, i + m - 1, 1);
        if (match(i + f, i + m - 1, 1 + f)) {
            ++ ans;
            continue;
        }
        f += find(i + f, i + m - 1, 1 + f);
        if (match(i + f, i + m - 1, 1 + f)) {
            ++ ans;
            continue;
        }
        f += find(i + f, i + m - 1, 1 + f);
        if (match(i + f, i + m - 1, 1 + f)) {
            ++ ans;
            continue;
        }

    }
    cout << ans;
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0), cout.tie(0);

    int T;
    cin >> T;
    while (T --) {  
        clear();
        cin >> (R + 1) >> (S + 1);
        n = strlen(R + 1);
        m = strlen(S + 1);
        solve();
    }
    return 0;
}