Z Algorithm Problem Statement

You are provided with a string S of length N and a string P of length M. Your objective is to determine the number of times P appears in S in linear time.

Example:

Input:

S = "ababa", P = "ab"

Output:

2

Explanation:

The string "ab" occurs twice in the string "ababa".

Constraints:

• The string consists only of lowercase English alphabets.
• 1 <= T <= 100
• 1 <= N, M <= 10^4
• Time Limit: 1 sec

Input:

The first line of input contains T, the number of test cases.
The first line of each test case contains two integers N and M, representing the lengths of strings S and P respectively.
The second line of each test case contains the string S.
The third line of each test case contains the string P.

Output:

The output for each test case is a single integer indicating the number of occurrences of P in S.

Note:

You do not need to print anything; it has already been handled. Simply implement the function to return the result.