Maximum Distinct Substrings

You are given a string (S) and a list of queries. Each query is an integer (X). For each query, calculate the number of distinct substrings of length (X) in (S). If (X > |S|), then the answer is 0.

For instance, consider (S = \texttt{abacaba}) and (X = 3). The substrings of length 3 are: (aba), (bac), (aca), (cab), and (aba) again. Hence, the distinct substrings are (aba), (bac), (aca), and (cab) with a total of 4 distinct substrings.

inputFormat

The first line of the input contains an integer (T) denoting the number of test cases. For each test case, the first line contains two integers (N) and (Q), where (N) is the length of the string and (Q) is the number of queries. The next line contains the string (S). The following line contains (Q) space-separated integers, each representing a query with substring length (X).

outputFormat

For each test case, output a single line with (Q) space-separated integers, where each integer is the number of distinct substrings of length (X) for the corresponding query.## sample

2
7 3
abacaba
3 2 4
5 2
abcde
1 3

4 4 4
5 3