406008 - 寻找子串

有两个全部由大写字母组成的字符串S1和S2,求S1在S2中出现的次数。

Input

输入有多组数据,每组数据第一行为字符串S1,第二行为字符串S2。

Output

每行一个整数,表示匹配次数。

Examples

Input

3
BAPC
BAPC
AZA
AZAZAZA
VERDI
AVERDXIVYERDIAN

Output

1
3
0
Time Limit 1 second
Memory Limit 128 MB
Stats
上一题 下一题