Unique Substrings Counting

You are given a string s and several queries. Each query provides an integer k. For each query, you must determine the number of unique substrings of length k in the string s.

A substring is a contiguous sequence of characters in a string. For example, for s = "abcabc" and k = 3, the unique substrings are: \(abc\), \(bca\), and \(cab\), so the answer is 3.

You will be given multiple test cases. For each test case, first you are given the string, then the number of queries, and then each query on a separate line.

Input Format: The first line contains an integer \(T\), the number of test cases. The description for each test case follows:

• A line containing the string s.
• A line containing an integer \(Q\), the number of queries.
• \(Q\) lines follow, each containing an integer \(k\).

Output Format: For each query in the order given, print the number of unique substrings of length \(k\> in s on a new line.

inputFormat

The input is read from standard input and follows this format:

T
s_1
Q_1
k_1
k_2
... (Q_1 values)
s_2
Q_2
k_1
k_2
... (Q_2 values)
...
s_T
Q_T
k_1
k_2
... (Q_T values)

Where T is the number of test cases.

outputFormat

For each test case, output the answer for each query on a separate line. The answers for all the test cases should be output in the same order as the queries are given in the input.

## sample

4
abcabc
2
1
3
abcd
2
2
3
aaaa
2
1
2
abcde
1
5

3
3
3
2
1
1
1

</p>