Description

给定一个主串和一个模式串，要求计算模式串在主串中出现的次数。字符串长度不超过 $10^6$。

Input

第一行给出测试组数 $T$，表示接下来有 $T$ 组数据。
每组数据包含两行：

• 第一行为模式串。
• 第二行为主串。

Output

对于每组数据，输出模式串在主串中出现的次数。

3
BAPC
BAPC
AZA
AZAZAZA
VERDI
AVERDXIVYERDIAN

1
3
0

Explanation

• 在第一组数据中，模式串 BAPC 在主串 BAPC 中出现了 $1$ 次。
• 在第二组数据中，模式串 AZA 在主串 AZAZAZA 中出现了 $3$ 次（重叠部分也算）。
• 在第三组数据中，模式串 VERDI 在主串 AVERDXIVYERDIAN 中未出现，因此输出 $0$。