你被给定一条由周期性重复字符串 $A$ 覆盖的无限长直线（直线上有无穷多个 $A$ 的拼接）。这条直线没有起点也没有终点。你被给定一个包含 $M$ 个字符串的集合 $S$。你需要通过拼接 $S$ 中的字符串来构建一个新的字符串 $B$。字符串 $B$ 必须满足以下条件：

• 用无穷多个 $B$ 拼接覆盖一条新的空白无限长直线后，该直线应与字符串 $A$ 完全相同。
• 如果存在多个合法的字符串 $B$ 或多种构建 $B$ 的方式，你应该选择能使 $S$ 中字符串使用次数最少的 $B$ 及其构建方式。

你可以多次使用 $S$ 中的同一个字符串，但每次使用都计为一次新的字符串使用。你可以以任意顺序拼接这些字符串，但你不能改变字符串中字母的顺序。如果无法构建出合法的字符串 $B$，请输出 $-1$。

输入格式

• 第一行包含字符串 $A$ ($1 \le |A| \le 500$)。
• 第二行包含整数 $M$ ($1 \le M \le 10^5$)，表示集合 $S$ 中字符串的数量。
• 接下来的 $M$ 行，每行包含 $S$ 中的一个字符串，第 $i$ 行包含字符串 $L_i$ ($1 \le |L_i| \le |A|$)。集合 $S$ 中所有字符串的长度之和小于 $10^6$ ($\sum_{i=1}^M |L_i| \le 10^6$)。

输出格式

输出一个整数，表示构建字符串 $B$ 所需的 $S$ 中字符串的最少实例数量。

样例

输入 1

baabaa
3
a
b
c

输出 1

3

说明

你可以使用一个字符串 "b" 和两个字符串 "a" 来构建 $B = \text{"aba"}$： ...baabaabaabaa... .....abaabaabaaba...