题目描述

给出两个字符串$s_1,s_2$（(只有大写字母），求$s_1$在$s_2$中出现多少次。 例如：$s_1="ABA"$,$s_2="ABAABA"$,答案为$2$。

输入

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

输出

如题述。

输入样例

3
BAPC
BAPC
AZA
AZAAZAAZA
VEEDI
AVERDXIVYERDLAN

输出样例

1
3
0

提示

$1≤s_1$的长度 $≤10^4$​​ ，$1≤s_2$的长度 $≤10^6$​ 。

评测数据说明

本题使用按题意独立构造、双实现核对的训练数据，共10个测试点，非原站或官方原始数据。总分100分。