Дано рядок і шаблони. Підрахуйте для кожного шаблону кількість позицій, де він з’являється в рядку.

Обмеження

• \(1≤n≤10^5\)
• \(1≤k≤5⋅10^5\)
• загальна довжина візерунків не перевищує \(5 ⋅10^5\)

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

У першому рядку вхідних даних є рядок довжиною \(n\).

Наступний рядок містить ціле число \(k\): кількість шаблонів.

Нарешті, є \(k\) рядків, які описують шаблони.

Рядок і шаблони складаються з символів 'a'–'z'.

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

Для кожного шаблона виведіть кількість позицій.

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

aybabtu
3
bab
abc
a

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

1
0
2