Cutting

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

Визначити, за яку мінімальну кількість операцій можна знищити весь рядок S. Гарантується, що це можна зробити.

Вхідні дані

У першому рядку слово S. У другому рядку ціле число N — кількість слів у списку. Далі N рядків, у кожному з яких по одному слову зі списку M. Усі слова складаються лише з рядкових латинських літер.

Вихідні дані

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

Обмеження

1 ≤ |S| ≤ 100

1 ≤ N ≤ 100

1 ≤ |M_i| ≤ 100

Приклади