Description

众所周知，追求小众是一件很大众的事。

Orange有 $n$ 个朋友，大家约定了周末一起出门玩。每个朋友都会携带一个字符串 $S_i$。为了追求小众，Orange决定从自己的字符串 $P$ 中挑选一段子串 $\hat P$，使得任何 $S_i$ 都不是 $\hat P$ 都子串。请问Orange能选出的最长 $\hat P$ 的长度是多少？

子串：我们把字符串中连续的一段子序列称为子串。

Format

Input

输入第1行包含一个字符串 $P$。

输入第2行包含1个整数 $n$，表示Orange朋友的数量。

接下来 $n$ 行，每行均包含一个字符串 $S_i$。

数据范围

对于 30% 的数据：

$|P| \le 1000$

$\sum |S_i| \le 100$

对于所有数据：

$|P| \le 10^5$

$n \le 10$

$\sum |S_i| \le 10^5$

保证所有字符串仅包含大小写字母。

Output

输出一个整数表示答案。

Samples

Go_straight_along_this_street
5
str
long
tree
biginteger
ellipse

12