题目描述

法国作家 Georges Perec (1936–1982) 曾经写了一本名为 《La disparition》 的书，这部作品通篇没有包含字符 'e'。作家 Georges Perec 是 Oulipo 组织的一名成员，在书中，他说道：

一切看似都正常合理，但一切又都证明是虚假的。起初，一切似乎都平常无奇，随后却突然冒出非人的、令人惊恐的东西。他本想知道，将他与这部小说联系起来的那种关联究竟体现在何处：在他的地毯上，无时无刻不冲击着他的想象，一种禁忌的直觉，一种阴暗邪恶的幻象，一种空虚之物、一种未言明之事的幻象：那种掌控一切的遗忘的幻象、非幻象，在那里理性不复存在：一切看似正常，然而……

Perec 在接下来的这场比赛中很可能会取得高分（或者更确切地说，低分）。比赛要求人们就某个主题撰写一篇或许甚至要有意义的文本，同时尽可能少地出现某个特定 “单词”。我们的任务是为评审团提供一个程序，用于统计这些特定 “单词” 的出现次数，以便对参赛者进行排名。这些参赛者常常会写出毫无意义却篇幅极长的文本；连续出现 50 万个 “T” 这样的情况并不罕见。而且他们从不使用空格。

所以我们希望能快速查明一个单词，也就是一个给定的字符串，在一篇文本中出现的次数。更正式地表述为：给定字母表 {'A', 'B', 'C', …, 'Z'} 以及基于该字母表的两个有限字符串，一个单词 W 和一篇文本 T，统计单词 W 在文本 T 中出现的次数。单词 W 的所有连续字符必须与文本 T 中的连续字符完全匹配。这些出现情况可能会有重叠。

输入

第 1 行包含了一个整数 $g$，表示有 $g$ 组数据

每组数据包含两行字符串 $W$ 和 $T$ ，要求查找 $W$ 在 $T$ 种的出现次数 （$1 \le |W| \le |T| \le 20,000$）。 $W$ 和 $T$ 值包含 {‘A’, ‘B’, ‘C’, …, ‘Z’} 字符。

输出

对于每一组测试数据，输出一行整数，为该组数据中 $W$ 在 $T$ 内出现的次数。

样例

3
BAPC
BAPC
AZA
AZAZAZA
VERDI
AVERDXIVYERDIAN

1
3
0