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

Submit: 2426 Solved: 448

[Submit][Status][Web Board]

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

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.

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

```
2
15
chenljnbwowowoo
2
wo
14
touristrealgod
7
tourist
```

```
3
1
```

Easy problem.