УЛІПО
Одного разу французський автор Жорж Перек (1936–1982) написав книгу La disparition без літери 'e'. Він був членом групи УЛІПО (фр. OULIPO, скорочення від Ouvroir de littérature potentielle - об'єднання письменників і математиків, які поставили своєю ціллю наукове дослвдження потенційних можливостей мови шляхом вивчення відомих і створення нових штучних літературних обмежень, під якими розуміються довільні формальні вимоги до художнього тексту). Цитата з книги:
Tout avait Pair normal, mais tout s’affirmait faux. Tout avait Fair normal, d’abord, puis surgissait l’inhumain, l’affolant. Il aurait voulu savoir où s’articulait l’association qui l’unissait au roman : stir son tapis, assaillant à tout instant son imagination, l’intuition d’un tabou, la vision d’un mal obscur, d’un quoi vacant, d’un non-dit : la vision, l’avision d’un oubli commandant tout, où s’abolissait la raison : tout avait l’air normal mais…
Перек можливо отримав би вищий (або навпаки, нижчий) бал у наступному змаганні. Необхідно написати текст (можли навіть безглуздий) на деяку тему, у якому якомога рідше зустрічається задане "слово". Журі необхідно подати програму, яка підраховує кількість входжень цього слова у текст, таким чином встановивши рейтинг конкурсантів. Учасники за звичай пишуть довгі безглузді тексти; наприклад текст, який складається з 500,000 послідовних літер 'T' не є незвичайним. І ще вони ніколи не використовують пропуски.
Ми хочемо швидко відповідати на питаня як часто слово, тобто заданий рядок, зустрічається у тексті. Більш формально: є алфавіт {'A', 'B', 'C', …, 'Z'} і два скінчинних рядки над ним - слово W і текст T. Необхідно підрахувати скільки разів W зустрічається в T. Усі послідовні символи W повинні у точності співпадати з послідовними символами T. Входження слів можуть перетинатись.
Вхідні дані
Перший рядок містить кількість тестів. Кожен тест має наступний формат:
Перший рядок містить слово W, записане у алфавіті {'A', 'B', 'C', …, 'Z'}, де 1 ≤ |W| ≤ 10000 ( |W| означає довжину рядка W).
Другий рядок задає текст T, записаний у алфавіті {'A', 'B', 'C', …, 'Z'}, где |W| ≤ |T| ≤ 1000000.
Вихідні дані
Для кожного тесту виведіть у окремому рядку одне число - кількість входжень слова W у текст T.