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

Background

Special for beginners, ^_^

Description

给出两个字符串 $s_1（长度不超过10^6）,s_2（长度不超过10^6）$（只有大写字母），求 $s_1$ 在 $s_2$ 中出现多少次。

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

Format

Input

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

Output

如题述。

Samples

3
BAPC
BAPC
AZA
AZAAZAAZA
VEEDI
AVERDXIVYERDLAN

1
3
0

Limitation

1s, 1024KiB for each test case.