题目描述

给出两个字符串S1，S2（只有大写字母），求S1在S2中出现了多少次。
例如S1=“ABA”，S2=“ABABA”，答案为2。

输入格式

输入T组数据，每组数据保证strlen(S1)<=10^4,strlen(S2)<=10^6,0<T<=10。

输出格式

输出每组S1在S2中出现了多少次。

样例数据

input

3
BAPC
BAPC
AZA
AZAZAZA
VERDI
AVERDXIVYERDIAN

output

1
3
0