Одного разу французський автор Жорж Перек (1936--1982) написав книгу La disparition без літери '\textbf{e}'. Він був членом групи УЛІПО (фр. OULIPO, скорочення від Ouvroir de littérature potentielle - об'єднання письменників і математиків, які поставили своєю ціллю наукове дослвдження потенційних можливостей мови шляхом вивчення відомих і створення нових штучних літературних обмежень, під якими розуміються довільні формальні вимоги до художнього тексту). Цитата з книги: \textit{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…} Перек можливо отримав би вищий (або навпаки, нижчий) бал у наступному змаганні. Необхідно написати текст (можли навіть безглуздий) на деяку тему, у якому якомога рідше зустрічається задане "слово". Журі необхідно подати програму, яка підраховує кількість входжень цього слова у текст, таким чином встановивши рейтинг конкурсантів. Учасники за звичай пишуть довгі безглузді тексти; наприклад текст, який складається з \textbf{500,000} послідовних літер '\textbf{T}' не є незвичайним. І ще вони ніколи не використовують пропуски. Ми хочемо швидко відповідати на питаня як часто слово, тобто заданий рядок, зустрічається у тексті. Більш формально: є алфавіт \{'\textbf{A}', '\textbf{B}', '\textbf{C}', …, '\textbf{Z}'\} і два скінчинних рядки над ним - слово \textbf{W} і текст \textbf{T}. Необхідно підрахувати скільки разів \textbf{W} зустрічається в \textbf{T}. Усі послідовні символи \textbf{W} повинні у точності співпадати з послідовними символами \textbf{T}. Входження слів можуть перетинатись. \InputFile Перший рядок містить кількість тестів. Кожен тест має наступний формат: Перший рядок містить слово \textbf{W}, записане у алфавіті \{'\textbf{A}', '\textbf{B}', '\textbf{C}', …, '\textbf{Z}'\}, де \textbf{1} ≤ |\textbf{W}| ≤ \textbf{10000} ( |\textbf{W}| означає довжину рядка \textbf{W}). Другий рядок задає текст \textbf{T}, записаний у алфавіті \{'\textbf{A}', '\textbf{B}', '\textbf{C}', …, '\textbf{Z}'\}, где |\textbf{W}| ≤ |\textbf{T}| ≤ \textbf{1000000}. \OutputFile Для кожного тесту виведіть у окремому рядку одне число - кількість входжень слова \textbf{W} у текст \textbf{T}.