Background

disangan233 likes strings, so disangan333 wants you to find some strings that disangan233 likes.

Problem Description

In ChuanZhi’s development class, you are expected to develop a document processing software.

Given $T$ queries, each query provides $2$ strings $a, b$ of lengths $n, m$ consisting only of English letters. Find the number of occurrences of $a$ in $b$, where uppercase and lowercase of the same letter are not distinguished. Note that $a$ is a contiguous subsequence (substring) of $b$.

For all testdata, $T \leq 100$, $\sum n \leq \sum m \leq 10^3$. The strings consist only of uppercase or lowercase English letters.

Input Format

The input has a total of $3T + 1$ lines.

Line $1$ contains $1$ positive integer $T$.

Then there are $T$ groups of input, each group has $3$ lines.

Line $1$ contains $2$ positive integers $n, m$.

Line $2$ contains a string $a$ of length $n$.

Line $3$ contains a string $b$ of length $m$.

Output Format

Output $T$ lines. Line $i$ outputs $1$ integer, indicating the answer to query $i$.

5
3 10
abc
abcabcabca
2 10
aa
AAaAaaAaAa
5 5
AbCdE
eDcBa
5 5
abcde
ABCDE
3 10
aba
ABaBaAbaBA

3
9
0
1
4

Hint

For the first group of input, it appears $3$ times, namely [abc]abcabca, abc[abc]abca, abcabc[abc]a.

For the second group of input, it appears $9$ times, namely [Aa]AaaAaAa, A[aA]aaAaAa, Aa[Aa]aAaAa, AaA[aa]AaAa, AaAa[aA]aAa, AaAaa[Aa]Aa, AaAaaA[aA]a, AaAaaA[aA]a, AaAaaAa[Aa].

Translated by ChatGPT 5