#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 10;
typedef unsigned long long ull;

char s1[N], s2[N];
ull power[N], sum[N];
const ull base = 131;

int main() {
    power[0] = 1;
    for (int i = 1; i < N; i++) {
        power[i] = power[i - 1] * base;
    }

    int t;
    scanf("%d", &t);
    while (t--) {
        scanf("%s %s", s1 + 1, s2 + 1);

        int n = strlen(s1 + 1);
        int m = strlen(s2 + 1);

        sum[0] = 0;
        for (int i = 1; i <= m; i++) {
            sum[i] = sum[i - 1] * base + (s2[i] - 'A' + 1);
        }

        ull hash_s1 = 0;
        for (int i = 1; i <= n; i++) {
            hash_s1 = hash_s1 * base + (s1[i] - 'A' + 1);
        }

        int ans = 0;
        for (int i = 0; i <= m - n; i++) {
            ull sub_hash = sum[i + n] - sum[i] * power[n];
            if (sub_hash == hash_s1) {
                ans++;
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}