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!

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.

Print m integers − the i-th integer must equal r(C_i,s).