You are given a string and a list of words. For each word, your task is to count the number of occurrences in the string.

Input

The first line contains a string of length n that consists of characters A–Z.

The next line contains an integer w: the number of words.

Finally, there are w lines, each of which contains a word that consists of characters A–Z. The total length of the words is at most m.

Output

For each word, output the number of occurrences in the string.

Constraints

• 1 \le n,m \le 10^5

Example

Input:

AYBABTU
3
YBAB
B
XXX

Output:

1
2
0