字符串匹配

题目描述

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

例如：s1​="ABA"，s2​="ABABA"，输出为：2 。

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

测试数据保证：s1​ 的长度≤10⁴ ，s2​ 的长度≤10⁶ 。

输入

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

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

输出

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

样例

输入

3
BAPC
BAPC
AZA
AZAZAZA
VERDI
AVERDXIVYERDIAN

输出

1
3
0