Oulipo

The French writer Georges Perec (1936-1982) wrote a whole novel, La disparition, without ever using the letter 'e'. He belonged to the Oulipo group. A passage from the book:

Tout avait l’air normal, mais tout s’affirmait faux. Tout avait l’air normal, d’abord, puis surgissait l’inhumain, l’affolant. Il aurait voulu savoir où s’articulait l’association qui l’unissait au roman : sur son tapis, assaillant à tout instant son imagination, l’intuition d’un tabou, la vision d’un mal obscur, d’un quoi vacant, d’un non-dit : la vision, l’avision d’un oubli commandant tout, où s’abolissait la raison : tout avait l’air normal mais…

Perec would have scored high, or rather low, in the contest below. Entrants write a text on a given subject while making one given word appear as few times as possible. The jury needs a program that counts those appearances so the entrants can be ranked. Entrants often hand in very long texts with no meaning at all. A run of 500,000 consecutive 'T's is not unusual, and they never write spaces.

So we have to count quickly how often one string occurs inside another. Over the alphabet {'A', 'B', 'C', …, 'Z'} you are given a word $W$ and a text $T$. Count how many times $W$ occurs in $T$. Every character of $W$ must match consecutive characters of $T$ exactly. Occurrences may overlap.

The first line contains the number of test cases. Each test case has this format:

• One line with the word $W$, a string over {'A', 'B', 'C', …, 'Z'}, with $1 \le |W| \le 10^4$. Here $|W|$ is the length of $W$.
• One line with the text $T$, a string over the same alphabet, with $|W| \le |T| \le 10^6$.

For each test case, print the number of occurrences of $W$ in $T$ on a line of its own.