We'll call string $*s*[*a*, *b*] = *s*_{*a*}*s*_{*a* + 1}... *s*_{*b*}$ $(1 ≤ *a* ≤ *b* ≤ |*s*|)$ a substring of string $*s* = *s*_{1}*s*_{2}... *s*_{|*s*|}$, where $|*s*|$ is the length of string $*s*$.

The trace of a non-empty string $*t*$ is a set of characters that the string consists of. For example, the trace of string "aab" equals {'a', 'b'}.

Let's consider an arbitrary string $*s*$ and the set of its substrings with trace equal to $*C*$. We will denote the number of substrings from this set that are maximal by inclusion by $*r*(*C*, *s*)$. Substring $*s*[*a*, *b*]$ of length $*n* = *b* - *a* + 1$ belonging to some set is called maximal by inclusion, if there is no substring $*s*[*x*, *y*]$ in this set with length greater than $*n*$, such that $1 ≤ *x* ≤ *a* ≤ *b* ≤ *y* ≤ |*s*|$. Two substrings of string $*s*$ are considered different even if they are equal but they are located at different positions of $*s*$.

Polycarpus got a challenging practical task on a stringology exam. He must do the following: given string $*s*$ and non-empty sets of characters $*C*_{1}$, $*C*_{2}$, $...$, $*C*_{*m*}$, find $*r*(*C*_{*i*}, *s*)$ for each set $*C*_{*i*}$. Help Polycarpus to solve the problem as he really doesn't want to be expelled from the university and go to the army!

Input

The first line contains a non-empty string $*s*$ $(1 ≤ |*s*| ≤ 10^{6})$.

The second line contains a single integer $*m*$ $(1 ≤ *m* ≤ 10^{4})$. Next $*m*$ lines contain descriptions of sets $*C*_{*i*}$. The $*i*$-th line contains string $*c*_{*i*}$ such that its trace equals $*C*_{*i*}$. It is guaranteed that all characters of each string $*c*_{*i*}$ are different.

Note that $*C*_{*i*}$ are not necessarily different. All given strings consist of lowercase English letters.

Output

Print $*m*$ integers — the $*i*$-th integer must equal $*r*(*C*_{*i*}, *s*)$.