Ke Ke is a cheerful, enthusiastic girl. She dreams of singing happily every day. One day, while practicing singing, Ke Ke accidentally discovered that there are some words that can make the song better. She called these words "SuperstarWords".
After a lot of attempts, she found that in each song, there are a total of n "SuperstarWords". She wants to know the maximum number of disjoint occurrences of each "SuperstarWords" in her song.
Note : one occurrence means that the SuperstarWord is a continuous substring of the song at a certain position.
For example: The maximum number of disjoint occurrences of "aba" in "abababa" is 2
Input
The first line contains an integer T(T≤5), denoting the number of test cases.
The first line of each test case contains one string s(1≤|s|≤105), denoting a song.
The second line of each test case contains one integer n(1≤n≤105), denoting the number of SuperstarWords
The next n lines contains contains one string ai(1≤ |ai| ≤30), denoting one SuperstarWords
It is guaranteed that for all test cases, ∑|s|≤4∗105, ∑|ai|≤4∗105
Note:All input string character sets are lowercase English letters
Output
For each test case, output n lines, each line has one integer, indicating the answer.