Cutting

Дана строка S и список M, состоящий из N слов. За одну операцию можно выбрать некоторую подстроку строки S, если такая встречается в качестве слова в списке M, и вырезать из строки S. После чего оставшиеся части строки S, если такие есть, склеиваются.

Определить, за какое минимальное количество операций можно уничтожить всю строку S. Гарантируется, что это можно сделать.

Входные данные

В первой строке слово S. Во второй строке целое число N — количество слов в списке. Далее N строк, в каждой из которых по одному слову из списка M. Все слова состоят только из строчных латинских букв.

Выходные данные

Одно число — минимальное количество операций, необходимое для уничтожения строки S.

Ограничения

1 ≤ |S| ≤ 100

1 ≤ N ≤ 100

1 ≤ |M_i| ≤ 100

Примеры