字符串匹配

给定2个仅包含大写字母的字符串s1,s2，求出s1在s2中出现的次数。
例如：s1="ABA"，s2="ABABA"，输出为：2。
输入T组数据（T≤20），对每组数据输出结果。
测试数据保证：s1的长度≤10⁴，s2的长度≤10⁶。

输入文件的第一行包含一个整数T，表示测试数据的有多少组。
对于每组数据，先输入一行仅包含大写英文字母的字符串s1，再输入一行仅包含大写英文字母的字符串s2。

输出有T行，每行一个整数，代表每组数据的计算结果。

3
BAPC
BAPC
AZA
AZAZAZA
VERDI
AVERDXIVYERDIAN

1
3
0