题目描述

给定两个非空小写字母串 $A$ 和 $B$。请统计 $B$ 作为连续子串在 $A$ 中出现了多少次。

如果两次出现的位置不同，即使它们有重叠，也需要分别计数。

输入格式

第一行输入测试组数 $T$。

每组数据包含两行，第一行是字符串 $A$，第二行是字符串 $B$。

输出格式

对每组数据输出 Case x: ans，其中 $ans$ 表示 $B$ 在 $A$ 中出现的次数。

样例

4
axbyczd
abc
abcabcabcabc
abc
aabacbaabbaaz
aab
aaaaaa
aa

Case 1: 0
Case 2: 4
Case 3: 2
Case 4: 5

样例说明

数据范围

$1\le T\le 5$，$1\le |A|,|B|\le 10^6$。字符串只包含小写英文字母。