G. Substring Justice
time limit per test
4 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a string $$$S$$$ of length $$$N$$$ and a set of $$$M$$$ strings $$$\{T_1, T_2, \dots, T_m\}$$$.

You want to select as many non-overlapping substrings$$$^\dagger$$$ of $$$S$$$ as possible such that each selected substring is exactly equal to one of the $$$M$$$ strings.

$$$\dagger$$$  Substring: obtained by deleting several (possibly zero) characters from the start of the string and several (possibly zero) characters from the end of the string.

Input

The first line of the input contains a single integer $$$T$$$ ($$$1 \le T \le 10^5$$$) — the number of testcases.

The first line of each testcase contains two space-separated integers $$$N$$$ and $$$M$$$ ($$$1 \le N, M \le 10^5$$$).

The second line of each testcase contains the string $$$S$$$ of length $$$N$$$, consisting of lowercase English letters.

Each of the next $$$M$$$ lines contains one string $$$T_i$$$ ($$$1 \le |T_i| \le 20$$$).

It is guaranteed that $$$\sum_{i=1}^{M} |T_i|$$$ over all the testcases does not exceed $$$4 \cdot 10^5$$$.

It is guaranteed that $$$\sum |S|$$$ over all test cases does not exceed $$$ 2 \cdot 10^5$$$.

Output

Output $$$T$$$ lines each containing a single integer — the maximum number of pairwise non-overlapping substrings of $$$S$$$ such that each substring equals one of the $$$M$$$ given strings.

Example
Input
2
7 2
arwhwar
ar
w
7 1
arwhwar
ar
Output
4
2