Problem C: Kate Make Program [Easy]

Problem C: Kate Make Program [Easy]

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 2426  Solved: 448
[Submit][Status][Web Board]

Description

Give you a text S and a pattern P. You should print how many times P appears in S.

Input

The first line will be an integer T, which is the number of test cases. (1 <= T <= 10)

For each test case, the first line will be an integer n, which is the length of the text string.

Then a line contains a text string S. |S| <= 1000000

The third line will be an integer m, which is the length of the pattern string.

Then a line contains a pattern string P. |P| <= |S|

S and will only contain lower case English letters.

Output

Print a number in a single line for each test case, which means how many times P appears in S.

Sample Input

2
15
chenljnbwowowoo
2
wo
14
touristrealgod
7
tourist

Sample Output

3
1

HINT

Easy problem.

[Submit][Status]