G. Most Common Suffix
time limit per test
1 second
memory limit per test
512 megabytes
input
standard input
output
standard output

You are given n strings, and q queries. For each query i, your task is to find the most common suffix of length xi, you need to print how common it is.

The suffix i (or the ith suffix) of a string is a special case of substring that goes from the ith character of the string up to the last character of the string. For example, the 4th suffix of "development" is "lopment", the 7th suffix of "development" is "ment" (0-based indexing).

Input

The first line contains an integer T (1 ≤ T ≤ 75), where T is the number of test cases.

The first line of each test case contains two integers n and q (1 ≤ n, q ≤ 104), where n is the number of strings, and q is the number of queries.

Then n lines follow, each line contains a string s, giving the strings. All strings are non-empty consisting of lowercase English letters.

Then q lines follow, each line contains an integer x (1 ≤ x ≤ m), giving the queries. Where m equals the length of the longest string among the given n strings.

The total length of strings in each test case does not exceed 105.

Output

For each query, print a single line containing the answer.

Example
Input
1
5 4
abccba
abddba
xa
abdcba
aneverknow
1
2
4
3
Output
4
3
1
2
Note

As input/output can reach huge size it is recommended to use fast input/output methods: for example, prefer to use scanf/printf instead of cin/cout in C++, prefer to use BufferedReader/PrintWriter instead of Scanner/System.out in Java.