Problems
Cutting
Cutting
You are given string S and list M, consisting of N words. During an operation you may choose substring of string S, if it can be found as word in list M, and cut it out of string S. Then remaining parts of string S, are merged if there are any.
Determine minimal amount of opertions required to erase whole string S. It is guaranteed that it can be done.
Input data
The rst line contains word S. Second line contains integer N, amount of words in the list. It is followed by N lines listing words from M. All words consist of lowercase latin letters only.
Output data
One integer, that is minimal number of opertions required to erase whole string S.
Limits
1 ≤ |S| ≤ 100
1 ≤ N ≤ 100
1 ≤ |M_i| ≤ 100
Examples
Input example #1
abacaba 4 aba aca a b
Output example #1
3