Polycarpus is Looking for Good Substrings

4000ms

262144K

Description:

We'll call string s[a, b] = s_as_a + 1... s_b (1 ≤ a ≤ b ≤ |s|) a substring of string s = s₁s₂... 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₁, C₂, ..., 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⁶).

The second line contains a single integer m (1 ≤ m ≤ 10⁴). 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).

Sample Input:

aaaaa
2
a
a

Sample Output:

1
1

Sample Input:

abacaba
3
ac
ba
a

Sample Output:

1
2
4

Informação

Provedor Codeforces

Código CF212B