Несколько дней назад WJMZBMR научился быстро отвечать на запрос «сколько раз строка x встречается в строке s», путем предварительной обработки строки s. Но сейчас он хочет немного усложнить этот запрос.
Итак, его новый запрос: «сколько последовательных подстрок s циклически изоморфны данной строке x». Вам дана строка s и n строк xi, для каждой строки xi найдите количество последовательных подстрок s, циклически изоморфных строке xi.
Две строки называются циклически изоморфными, если одну из них можно получить из другой путем вращения. Здесь под вращением имеется в виду перемещение некоторого количества подряд идущих символов (возможно, это количество равняется нулю) из начала строки в конец строки в том же порядке. Например, строку «abcde» можно вращением превратить в строку «deabc». Мы можем взять символы «abc» из начала строки и поставить их в конец после «de».
Выходные данные
Для каждого запроса xi выведите единственное целое число — количество последовательных подстрок в s, которые циклически изоморфны xi. Выводите ответы на запросы в том порядке, в котором запросы заданы во входных данных.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
baabaabaaa
5
a
ba
baa
aabaa
aaba
|
7
5
7
3
5
|
|
2
|
aabbaa
3
aa
aabb
abba
|
2
3
3
|