Votka loves string very much. Recently he learned prefixes and suffixes. A prefix of a string S is any leading contiguous part of S and a suffix of string S is any trailing contiguous part of S, e.g., the prefixes of string “abc” are { “a”, “ab”, “abc” } and the suffixes are { “abc”, “bc”, “c” }. Votka considers a suffix Si of string S beautiful, if Si has at least b prefixes which are also prefixes of S.

Formally,
let, P = the set of prefixes of the string S
Pi = the set of prefixes of the suffix Si
Then, Si is a beautiful suffix if |P ∩ Pi| ≥ b.

For example, consider S = “abcabcd” and b = 3, then suffix S3 i.e. “abcd” is a beautiful suffix because it has 3 (≥ b) prefixes { “a”, “ab”, “abc” } which are also prefixes of S. Note that, S itself is a beautiful suffix for all b ≤ |S|.

Now Votka thinks about a problem. The problem is, you are given a string S and m numbers {K1, K2, … , Km }. For each number K_i, you have to find the number of beautiful suffixes of S considering b = K_i.

Votka announces that he will give a treat to the first solver of this problem. Luffy, a close friend of Votka, wants to have that treat. As Luffy is very dumb, he asks for your help. Can you help him? :)

Input

Input starts with an integer T (≤ 10), denoting the number of test cases. The first line of each case contains a string S (1 ≤ |S| ≤ 100000). S contains only lowercase English letters. The next line contains an integer m (1 ≤ m ≤ 100000). The following line contains m space separated integers K1, K2, … , Km (0 ≤ K_i ≤ 100000).

Output

For each test case, print m space separated integers (number of beautiful suffixes of S considering b = K_i) in a single line. (Caution: Dataset is large. Use faster I/O. )

Sample

Input:
2
abcabcd
3
3 7 8
aaaaa
5
1 2 3 4 5
Output:
2 1 0
5 4 3 2 1