Злови мене, якщо зможеш
Після перегляду фільму "Злови мене, якщо зможеш", професор Махаммад вирішив створити нову задачу для своїх програмістів. Оскільки деякі процедури в його дослідженні значною мірою залежать від порівняння рядків, він хоче перевірити навички своїх початківців-програмістів у цій сфері. Завдання дуже просте: професор надає вам випадковий рядок і кілька запитів. Для кожного рядка запиту ви повинні підрахувати, скільки разів він зустрічається в рядку, наданому професором.
Вхідні дані
Перша строка вхідних даних містить два додатні цілі числа n (n ≤ 3000) і q, які визначають довжину рядка професора та кількість запитів відповідно. Друга строка містить рядок професора довжиною n. Наступні q строк містять рядки запитів ненульової довжини.
Сума довжин рядків запитів не перевищує 500000.
Вихідні дані
Для кожного запиту виведіть кількість його входжень у рядку професора.