Description

给定文本串s与模式串t，求s中有多少个子串与t相同，两个子串视为不同仅当他们长度不等或起始位置不同。

Input

第一行输入T(T<=100)表示有T组数据。每组数据输入两行字符串，即为s、t,长度小于等于100000。

Output

输出T行正整数，第i行表示第i组文本串中有多少个子串与模式串相同。

Sample Input

2
ababa
aba
aaa
a

Sample Output

2
3