String Factorization

Let A be a finite alphabet. Let T be a string over A. We say that a sequence of unempty strings f(T) = (s₁, s₂, ..., s_k) is a factorization of T if the concatenation s₁s₂...s_k is identical with T. We say that each string s_i (1 ≤ i ≤ k ) is an element of f(T) or a factor of T. Note that f(T) is a sequence, therefore some of its elements might be equal to one another.
Let D be a dictionary of words over A. We define the D-size of f(T) as the cardinality of the set {i ∈ N | s_i ∈ f(T) ∧ s_i ∈ D}.

The task

You are given a dictionary D and a string T. Determine the maximum possible D-size of a factorization of T.

---

Input

The first input line contains one string T. Next line contains a single integer ND which represent the number of words in the given dictionary D. Next, there are ND lines, each of which contains one word in D. The alphabet of T and D is the set of small english letters {a, b, c, ..., z }. There are no other symbols or blanks in T or in D. The order of words in D in the input is arbitrary, some words in D might be identical.
It holds, 1 ≤ length(T) ≤ 10⁶, 1 ≤ ND ≤ 10³. The length of any word in D is at least 1 and at most 500.

Output

The output is one line with a single integer denoting the maximum possible value of the D-size of a factorization of input string T.

Example 1

Input

daaabcdaaadaaabcdaaa
4
aa
daa
bcd
abc

Output

6

The D-size of the factorization (daa, a, bcd, aa, ada, aa, bcd, a, aa ) of the input string T is 6, the factors of T which are also elements of D are printed in bold italics. There are other factorizations of T which D-size is 6, there is no factorization of T which D-size is 7 or more.

Example 2

Input

abababababa
3
aba
bab
abab

Output

3

The D-size of the factorization (aba, b, aba, b, aba ) of the input string T is 3, the factors of T which are also elements of D are printed in bold italics. There are other factorizations of T which D-size is 3, there is no factorization of T which D-size is 4 or more.

Example 3

Input

abcdefgfgfdcb
6
abc
bcde
def
fdcb
fg
gfgf

Output

4

The D-size of the factorization (a, bcde, fg, fg, fdcb ) of the input string T is 4, the factors of T which are also elements of D are printed in bold italics. There is another factorization of T which D-size is 4, there is no factorization of T which D-size is 5 or more.

---

Public data

The public data set is intended for easier debugging and approximate program correctness checking. The public data set is stored also in the upload system and each time a student submits a solution it is run on the public dataset and the program output to stdout and stderr is available to him/her.
Link to public data set