McFn interesed in string problem recently.He found a interesing function and he felt he could use this function to invent a new match algorithm.

For a string S [1 ... n] and i ¡Ê [1, n], define F (i) is the length of the longest common suffix of S and S [1 ... i].
For example, for the string S [1 ... 11] = zaaxbaacbaa, then F (1) = 0, F (2) = 1, F (3) = 2 (note that S [1 ... 3] = zaa), F (4) = 0, ... ... F (10) = 1, F (11) = 11;
For the string S [1 ... n], i ¡Ê [1, n], S [i ... n] is its suffix;

Input

The first line is a integer T.the number of test cases
for each test case
The first line is a string S, composed of only lowercase letters,  len (s) is the length of s,  1 <= len (s) <= 1000000;
Next line, a number N (1 <= N <= 100000), denote that the number of quiries;
The next N lines, each line contains a number x (1 <= x <= len (s)).

Output

For each x the output F (x);

Example

Input:
1
zaaxbaacbaa
11
1
2
3
4
5
6
7
8
9
10
11

Output:
0
1
2
0
0
1
3
0
0
1
11