No tag edit access

B. Polycarpus is Looking for Good Substrings

time limit per test

4 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputWe'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*).

Examples

Input

aaaaa

2

a

a

Output

1

1

Input

abacaba

3

ac

ba

a

Output

1

2

4

Codeforces (c) Copyright 2010-2017 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Sep/22/2017 09:05:26 (c3).

Desktop version, switch to mobile version.

User lists

Name |
---|