Count Substring Occurrences

In this problem, you are given two strings ( S ) and ( T ). Your task is to compute the number of times the string ( T ) appears as a contiguous substring in ( S ). Occurrences may overlap. For example, if ( S = \texttt{aaaaa} ) and ( T = \texttt{aa} ), then the answer is 4. Note that when ( T ) is an empty string, it is considered to occur ( |S|+1 ) times in ( S ).

inputFormat

The first line of input contains an integer ( N ), representing the number of test cases. Each test case consists of two lines: the first line contains the string ( S ) and the second line contains the string ( T ). Both strings may consist of any visible characters and can be empty.

outputFormat

For each test case, output a single line containing the number of times ( T ) appears as a contiguous substring in ( S ).## sample

3
ababcabc
abc
aaaaa
aa
hellohello
hello

2
4
2