Counting Patterns#2604

Counting Patterns

1 second
128 megabytes

Given a string and a set of patterns, determine for each pattern the number of positions at which it occurs in the string.

Input

The first line contains a string of length n~(1 \le n \le 10^5).

The second line contains an integer k~(1 \le k \le 5 \cdot 10^5) — the number of patterns. Each of the next lines contains one pattern. The total length of all patterns does not exceed 5 \cdot 10^5.

The string and the patterns consist of lowercase Latin letters '' - ''.

Output

For each pattern, print on a separate line the number of its occurrences in the string.

Examples

Example 1

Loading
Loading