Однажды французский автор Жорж Перек (1936--1982) написал книгу La disparition без буквы '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}.