题目描述

给定 $2$ 个仅包含大写字母的字符串 $s_1,s_2$ ，求出 $s_1$ 在 $s_2$ 中出现的次数。

例如： $s_1="ABA"$ ， $s_2="ABABA"$ ，输出为： $2$ 。

输入 $T$ 组数据（ $T≤20$ ），对每组数据输出结果。

测试数据保证： $s_1$ 的长度 $≤10^4$ ， $s_2$ 的长度 $≤10^6$ 。

输入

输入的第一行包含一个整数 $T$ ，表示测试数据的有多少组。

对于每组数据，先输入一行仅包含大写英文字母的字符串 $s_1$ ，再输入一行仅包含大写英文字母的字符串 $s_2$ 。

输出

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

样例

3
BAPC
BAPC
AZA
AZAZAZA
VERDI
AVERDXIVYERDIAN

1
3
0

来源

POJ