#include <stdio.h>
#include <cstring>
#define MAX_N	10000
#define MAX_M	1000000


int n, m;
char T[MAX_N + 1];
char S[MAX_M + 1];
int results[MAX_N + 1];


void init()
{
	results[1] = 0;

	for (int i = 2; i <= n; ++i) {
		int a = results[i - 1];

		while (true) {
			if (T[i - 1] == T[a]) {
				results[i] = a + 1;
				break;
			}
			if (a == 0) {
				results[i] = 0;
				break;
			}
			a = results[a];
		}
	}
}


int calc()
{
	int res = 0, curr = 0;

	for (int i = 0; i < m; ++i) {
		while (true) {
			if (S[i] == T[curr]) {
				if (++curr >= n) {
					++res;
					curr = results[curr];
				}
				break;
			}
			if (curr == 0) {
				break;
			}
			curr = results[curr];
		}
	}

	return res;
}


int main()
{
	int t; scanf_s("%d", &t);
	for (int i = 0; i < t; ++i) {
		scanf_s("%s", T, MAX_N + 1);
		scanf_s("%s", S, MAX_M + 1);		
		n = strlen(T), m = strlen(S);
		while (n < 1 || n > MAX_N || m < n || m > MAX_M) printf("...");

		init();
		printf("%d\n", calc());
	}
    return 0;
}