eolymp
bolt
Try our new interface for solving problems
Problems

Cutting

Cutting

Time limit 5 seconds
Memory limit 256 MiB

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

1N100

1 ≤ |M_i| ≤ 100

Examples

Input example #1
abacaba
4
aba
aca
a
b
Output example #1
3