E. Марсианские строки
ограничение по времени на тест
2 seconds
ограничение по памяти на тест
256 megabytes
ввод
стандартный ввод
вывод
стандартный вывод

За время своего изучения марсиан Петя хорошо понял, что марсиане крайне ленивые. Они любят спать и совсем не любят просыпаться.

Представьте себе марсианина имеющего ровно n глаз расположенных в ряд, и пронумерованных слева направо от 1 до n. Когда марсианин спит, он одевает на каждый свой глаз по повязке (чтобы утром марсианский свет не заставил его проснуться). С внутренней стороны каждой повязки написана одна прописная буква латинского алфавита, поэтому, когда марсианин утром просыпается и открывает все свои глаза, он видит строку s из прописных букв латинского алфавита длины n.

«Динь-дилинь!» — звонит будильник. Марсианин уже проснулся, но еще не открыл ни одного своего глаза. Он догадывается, что день сегодня будет трудным, поэтому ему хочется открыть глаза и увидеть что-нибудь хорошее. Марсианин считает, что только m слов марсианского языка красивые. Также с утра ему очень сложно открыть все глаза сразу, поэтому он открывает два не накладывающихся отрезка последовательных глаз. Более формально, марсианин выбирает четыре числа a, b, c, d (1 ≤ a ≤ b < c ≤ d ≤ n) и открывает все глаза с номерами i такими, что a ≤ i ≤ b или c ≤ i ≤ d. После того как марсианин открыл нужные ему глаза, он читает все видимые символы слева направо, получая тем самым какое-то слово.

Рассмотрим все различные слова, которые может увидеть с утра марсианин. Вам требуется узнать, сколько среди этих слов красивых.

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

В первой строке задана непустая строка s состоящая из прописных букв латинского алфавита, длиной n (2 ≤ n ≤ 105). Во второй строке задано целое число m (1 ≤ m ≤ 100) — количество красивых слов. В следующих m строках записаны красивые строки pi, состоящие из прописных букв латинского алфавита, длиной от 1 до 1000. Все красивые строки попарно различны.

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

Выведите одно целое число — количество различных красивых слов, которые может увидеть сегодня утром марсианин.

Примеры
Входные данные
ABCBABA
2
BAAB
ABBA
Выходные данные
1
Примечание

Рассмотрим тестовый пример. В нем можно получить только вторую красивую строку, если открыть отрезки глаз a = 1, b = 2 и c = 4, d = 5 или отрезки глаз a = 1, b = 2 и c = 6, d = 7. Первую красивую строку получить никак нельзя.