Count Occurrences of a Substring in a String (Case-Insensitive)

In this task, you are required to develop a document processing software. Given $T$ test cases, each test case consists of two strings:

• $a$: a string of length $n$ containing only English letters.
• $b$: a string of length $m$ containing only English letters.

Your goal is to count the number of times $a$ appears as a contiguous substring in $b$, ignoring the case (i.e. treating uppercase and lowercase letters as the same). For instance, if $a=\texttt{abc}$ and $b=\texttt{Abcabc}$, the correct answer would be $2$.

Note:

• $T \le 100$
• $\sum n \le 10^3$, $\sum m \le 10^3$

inputFormat

The first line of input contains an integer $T$, representing the number of test cases.

For each test case, there are two lines:

1. The first line contains the string $a$.
2. The second line contains the string $b$.

outputFormat

For each test case, output a single line containing the number of times $a$ appears in $b$ as a contiguous substring under case-insensitive matching.

sample

1
abc
abcabC

2