题目描述

这是一道模板题。

给定一个字符串S1 和一个字符串S2 ，求 S1 在 S2 中的出现次数。S1 和 S2 中的字符均为英语大写字母或小写字母。

S2中不同位置出现的 S1 可重叠。

例如：S1="ABA"，S2="ABABA"，答案为2

输入格式

输入T组数据，对每组数据输出结果

每组输入两行，分别是字符串 S1 和字符串S2 。

输出格式

输出每组对应一个整数，表示 S1 在S2 中的出现次数。

样例输入

1
zyz
zyzyzyz

样例输出

3

数据范围与提示

S1,S2的长度S1<=10^4 ，S2<=10^6、 S1,S2仅包含大小写字母。