A8592 | Polycarpus is Looking for Good Substrings

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!

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.

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