Вам дається рядок \(S\). Степан може виконати наступну операцію 0 або більше разів:

• Виберіть таке ціле число \(i\), що \(1 \leq i \leq |S|\), і змініть \(i\)-й символ \(S\) на *.

Мета Степана полягає в тому, щоб \(S\) не містив жодного з \(N\) рядків \(T_1,T_2,\ldots,T_N\) як підрядка.

Знайдіть мінімальну кількість операцій, необхідних для досягнення мети.

Обмеження

• \(1 \leq |S| \leq 5 \times 10^5\)
• \(1 \leq N\)
• \(N\) — ціле число.
• \(1 \leq |T_i|\)
• \(\sum{|T_i|} \leq 5 \times 10^5\)
• \(T_i \neq T_j\)якщо \(I \neq j\).
• \(S\) і \(T_i\) це рядки, що складаються з малих англійських літер.

Формат вхідних даних

Перший рядок містить \(S\)

Другий рядок містить ціле число \(N\)

Наступні  \(N\) рядків містять \(T_i\)

Формат вихідних даних

У вихідний потік виведіть відповідь.

Примітка

До прикладу 1:

Якщо він виконує операцію двічі, вибравши 1 і 9 для i, S стає *bcdefgh*jklmn; тепер він не містить abcd, ijk або ghi як підрядка.

Приклад вхідних даних

abcdefghijklmn 3 abcd ijk ghi

Приклад вихідних даних

2

Приклад вхідних даних

aaaaaaaaa
2
aa
xyz

Приклад вихідних даних

4