中文题面：

描述

法国作家乔治·佩雷克（1936–1982）曾写过一本名为《消失》的书，书中没有字母“$e$”。他是欧乌里波（Oulipo）小组的成员。书中的一句引用：

一切看起来都正常，但一切都显得虚假。起初，一切似乎都合理，然后出现了不人道、令人疯狂的部分。他曾想知道是哪种关联将他与小说联系在一起：

在他的地毯上，时刻侵袭着他的想象，是对禁忌的直觉，对模糊邪恶的想象，对空虚事物的想象，对未言明之事的想象：

这种想象，这种幻觉，是一种支配一切的遗忘，在这种遗忘中理性被废除：一切看起来都正常但……

佩雷克在下面的比赛中可能会得高分（或者应该说低分）。人们被要求就某个主题写一篇可能甚至有意义的文章，并且尽量少出现一个给定的“词”。

我们的任务是为评委提供一个程序来统计这些出现次数，以便对参赛者进行排名。

这些参赛者常常写非常长的文本，内容无意义；连续$50$万个'$T$'的序列并不罕见。而且他们从不使用空格。

因此，我们需要快速找出一个词（即给定的字符串）在文本中出现的次数。

更正式地说：给定字母表

{$'A'$, $'B'$, $'C'$, …, $'Z'$}

和两个有限长度的字符串，一个词$W$和一个文本$T$，计算$W$在$T$中出现的次数。

$W$的所有连续字符必须与T的连续字符完全匹配。出现可以重叠。

输入：

输入文件的第一行包含一个数字：表示后面的测试用例数量。每个测试用例的格式如下：

一行包含词W，这是一个由

{$'A'$, $'B'$, $'C'$, …, $'Z'$}

组成的字符串，且$1 ≤ |W| ≤ 10,000$（这里$|W|$表示字符串$W$的长度）。

一行包含文本$T$，这是一个由

{$'A'$, $'B'$, $'C'$, …, $'Z'$}

组成的字符串，且$|W| ≤ |T| ≤ 1,000,000$。

输出：

对于输入文件中的每个测试用例，输出应包含一个数字，占一行：词$W$在文本$T$中出现的次数。

输入数据 1

3
BAPC
BAPC
AZA
AZAZAZA
VERDI
AVERDXIVYERDIAN

输出数据 1

1
3
0

来源

北京算法程序设计竞赛 2006 资格赛