CF212B.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!

我们将字符串 $s[a, b] = s_a s_{a+1} \dots s_b$（其中 $1 \le a \le b \le |s|$）称为字符串 $s = s_1 s_2 \dots s_{|s|}$ 的一个子串，其中 $|s|$ 表示字符串 $s$ 的长度。

非空字符串 $t$ 的迹（trace） 是指该字符串所包含的字符构成的集合。例如，字符串 "aab" 的迹为 $\{ 'a', 'b' \}$。

考虑任意字符串 $s$ 及其所有迹等于 $C$ 的子串所组成的集合。我们用 $r(C, s)$ 表示该集合中按包含关系极大（maximal by inclusion）的子串个数。设某子串 $s[a, b]$ 长度为 $n = b - a + 1$，且属于该集合；若不存在该集合中的另一子串 $s[x, y]$，其长度大于 $n$，且满足 $1 \le x \le a \le b \le y \le |s|$，则称 $s[a, b]$ 是按包含关系极大的。即使两个子串内容完全相同，只要它们在 $s$ 中起始或终止位置不同，即视为不同的子串。

波利卡普斯在字符串学考试中获得了一道极具挑战性的实践题。他需要完成如下任务：给定字符串 $s$ 和若干非空字符集合 $C_1, C_2, \dots, C_m$，对每个集合 $C_i$，求出 $r(C_i, s)$。请帮助波利卡普斯解决这个问题吧——他真的不想被大学开除、然后去参军！

The first line contains a non-empty string s (1 ≤ |s| ≤ 106).

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

第一行包含一个非空字符串 $s$（$1 ≤ |s| ≤ 10^6$）。

第二行包含一个整数 $m$（$1 ≤ m ≤ 10^4$）。接下来的 $m$ 行描述集合 $C_i$。第 $i$ 行包含字符串 $c_i$，使得其字符集合（即所有不同字符组成的集合）等于 $C_i$。保证每个字符串 $c_i$ 中的所有字符互不相同。

注意：$C_i$ 之间不一定互不相同。所有给定的字符串均由小写英文字母组成。

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

输出 m 个整数——第 i 个整数必须等于 r(C__i, s)。