该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

给出两个字符串s1,s2（(只有大写字母），求s1在s2中出现多少次。

例如：s1="ABA",s2="ABAABA",答案为2。

输入格式

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

输出格式

如题述。

样例

输入样例

3
BAPC
BAPC
AZA
AZAAZAAZA
VEEDI
AVERDXIVYERDLAN

输出样例

1
3
0

提示

$\red {1≤s_1}$ 的长度 $\red{≤10^4}$​​ ，

$\red{1≤s_2}$的长度 $\red{≤10^6}$​ 。