题目描述

法国作家乔治·佩雷克（1936–1982）曾写过一本名为《消失》的书，整本书中没有出现字母 e。他是乌力波（Oulipo，潜在文学工场） 团体的成员。书中有这样一段话：

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，由大写字母组成，1 ≤ |W| ≤ 10,000（|W| 表示字符串 W 的长度）。
• 一行，包含文本 T，由大写字母组成，|W| ≤ |T| ≤ 1,000,000。

输出格式

对于每个测试用例，输出一行一个整数，表示单词 W 在文本 T 中的出现次数。

输入样例

3
BAPC
BAPC
AZA
AZAZAZA
VERDI
AVERDXIVYERDIAN

输出样例

1
3
0

来源

BAPC 2006 资格赛