C. Циклическая Задача
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Несколько дней назад WJMZBMR научился быстро отвечать на запрос «сколько раз строка x встречается в строке s», путем предварительной обработки строки s. Но сейчас он хочет немного усложнить этот запрос.

Итак, его новый запрос: «сколько последовательных подстрок s циклически изоморфны данной строке x». Вам дана строка s и n строк xi, для каждой строки xi найдите количество последовательных подстрок s, циклически изоморфных строке xi.

Две строки называются циклически изоморфными, если одну из них можно получить из другой путем вращения. Здесь под вращением имеется в виду перемещение некоторого количества подряд идущих символов (возможно, это количество равняется нулю) из начала строки в конец строки в том же порядке. Например, строку «abcde» можно вращением превратить в строку «deabc». Мы можем взять символы «abc» из начала строки и поставить их в конец после «de».

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

Первая строка содержит непустую строку s. Длина строки s не превышает 106 символов.

Вторая строка содержит целое число n (1 ≤ n ≤ 105) — количество запросов. Затем следуют n строк: в i-ой из них записана строка xi — строка для i-го запроса. Общая длина xi не превышает 106 символов.

В этой задаче строки состоят только из строчных букв латинского алфавита.

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

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

Примеры
Входные данные
baabaabaaa
5
a
ba
baa
aabaa
aaba
Выходные данные
7
5
7
3
5
Входные данные
aabbaa
3
aa
aabb
abba
Выходные данные
2
3
3