#include <algorithm>

#include <bitset>

#include <cctype>

#include <cerrno>

#include <clocale>

#include <cmath>

#include <complex>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <ctime>

#include <deque>

#include <exception>

#include <fstream>

#include <functional>

#include <limits>

#include <list>

#include <map>

#include <iomanip>

#include <ios>

#include <iosfwd>

#include <iostream>

#include <istream>

#include <ostream>

#include <queue>

#include <set>

#include <sstream>

#include <stdexcept>

#include <streambuf>

#include <string>

#include <utility>

#include <vector>

#include <cwchar>

#include <cwctype>

#include <stack>

#include <limits.h>

using namespace std;

#define MAXW 10010

#define MAXT 1000010

int T,l1,l2;

char s1[MAXW],s2[MAXT];

int next[MAXW];

template <typename T> inline void read(T &x) {

        int f = ; x = ;

        char c = getchar();

        for (; !isdigit(c); c = getchar()) { if (c == '-') f = -f; }

        for (; isdigit(c); c = getchar()) x = (x << ) + (x << ) + c - '';

        x *= f;

}

template <typename T> inline void write(T x) {

    if (x < ) { putchar('-'); x = -x; }

    if (x > ) write(x/);

    putchar(x%+'');

}

template <typename T> inline void writeln(T x) {

    write(x);

    puts("");

}

inline void getnext() {

        int i,pos;

        next[] = ;

        for (i = ; i <= l1; i++) {

                pos = next[i-];

                while (pos >  && s1[pos+] != s1[i]) pos = next[pos];

                if (s1[pos+] == s1[i]) next[i] = pos + ;

                else next[i] = ;

        }

}

inline void kmp() {

        int i,pos=,sum=;

        for (i = ; i <= l2; i++) {

                while (pos >  && s2[i] != s1[pos+]) pos = next[pos];

                if (s2[i] == s1[pos+]) pos++;

                else pos = ;

                if (pos == l1) sum++;

        }

        writeln(sum);

}

int main() {

        read(T);

        while (T--) {

                scanf("%s%s",s1+,s2+);

                l1 = strlen(s1+); l2 = strlen(s2+);

                getnext();

                kmp();

        }

        return ;

}