题目描述

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

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

输入格式

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

输出格式

如题述。

数据范围

$1 \le$ $s1$ 的长度 $\le 10^4$，$1 \le$ $s2$ 的长度 $\le 10^6$

测试样例

3
BAPC
BAPC
AZA
AZAAZAAZA
VEEDI
AVERDXIVYERDLAN

1
3
0