Дана строка S и список M, состоящий из N слов. За одну операцию можно выбрать некоторую подстроку строки S, если такая встречается в качестве слова в списке M, и вырезать из строки S. После чего оставшиеся части строки S, если такие есть, склеиваются.
Определить, за какое минимальное количество операций можно уничтожить всю строку S. Гарантируется, что это можно сделать.
В первой строке слово S. Во второй строке целое число N — количество слов в списке. Далее N строк, в каждой из которых по одному слову из списка M. Все слова состоят только из строчных латинских букв.
Одно число — минимальное количество операций, необходимое для уничтожения строки S.
Ограничения
1 ≤ |S| ≤ 100
1 ≤ N ≤ 100
1 ≤ |M_i| ≤ 100