Problem Description

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 "$Superstar Words$".

After a lot of attempts, she found that in each song, there are a total of $n$ "$Superstar Words$". She wants to know the $maximum$ number of $disjoint$ occurrences of each "$Superstar Words$" in her song.

$Note$ : one occurrence means that the $Superstar Word$ 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\leq5)$, denoting the number of test cases.

The first line of each test case contains one string $s(1\leq |s| \leq 10^5)$, denoting a song.

The second line of each test case contains one integer $n(1\leq n \leq 10^5)$, denoting the number of $Superstar Words$

The next $n$ lines contains contains one string $a_i$($ 1 \leq$ |$a_i$| $\leq 30 $), denoting one $Superstar Words$

It is guaranteed that for all test cases, $\sum |s| \leq 4*10^5$, $\sum |a_i| \leq 4*10^5$

$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.

2
abababbbaanbanananabanana
3
aba
ababa
nana
nihaoxiexiexiaolongbaozaijian
3
qwer
taihaotinleba
xiexi

2
1
2
0
0
1