该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目背景

本题和 Hard version 的区别在于：

呃，好像没有什么关系。甚至连出题人都不是同一个。

To the greatest All-around King zsp！

题目描述

伟大的查重专家 zsp 正在 find gpt.

In a contest, it's not good to ask gpt for help.

在一场比赛中，选手们会提交许多代码，其中一些代码会带有GPT生成所具有的特殊“痕迹”。你的任务是找出一共有多少个“痕迹”。

为了方便你的任务，zsp 事先将选手提交的代码转换成了一个仅含有小写字母的字符串 $s$，并将已知的“痕迹”转换成了一个仅含有小写字母的字符串 $t_i$。你需要输出 $t_i$ 在 $s$ 中匹配的次数。

匹配：指 $s$ 中存在一个连续子串 $s'$，使得 $s' = t$。对于不同的匹配，其位置应当不同。

输入格式

本题单个测试点内含有多组询问。

第一行一个正整数 $T$，代表询问次数。

对于每组询问：

第一行输入一行一个字符串 $s$，第二行输入一行一个字符串 $t$，意义如题目描述。

输出格式

对于每个询问，输出一行一个数字 $n$，表示痕迹匹配的次数。

样例 #1

样例输入 #1

2
iostreamcoutgpthelloendl
gpt
aaaaa
aa

样例输出 #1

1
4

提示

保证 $1 \leq T \leq 100$， $1 \leq |t| \leq |s| \leq 100$。