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.
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.
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