Now try to modify the algorithm to solve the following problem.

Given a string $t$ and $n$ queries, each query is a string $s_i$. For each request you need to count how many times the string $s_i$ occurs as a substring in $t$.

The first line of input contains the string $t\ (1≤|t|≤300,000)$.

The second line contains an integer $n$, the number of queries $(1≤n≤300,000)$. 

The following $n$ lines contain one non-empty line $s_i$ each. The sum of the lengths of all strings $s_i$ does not exceed $300,000$.

All strings consist of lowercase English letters.

For each request print one integer, the number of times the string $s_i$ occurs as a substring in $t$.