题目描述

输入两个字符串$S$和$T$，求$S$的 子串 中有多少个满足：$T$是该子串的一个 子序列 。
这里“子串”指的是原字符串中位置 连续 的一段，“子序列”指的是从原字符串中选取若干个字符（位置可以不连续），字符间相对位置不变，而形成的新字符串。例如原字符串为helloworld，则hell既是子串也是子序列，而lord是子序列但不是子串。

输入格式

第一行是一个正整数$K$，表示数据组数；
之后每组数据包含两行，依次为字符串$S$和$T$。字符串中只有小写字母。

输出格式

每组数据输出一行。输出一个非负整数表示答案。

样例

Input

5
abcdefg
a
abcdefg
d
abcdefg 
h
kokodayo
ka
hlkasjfhlkasjdhflkasjdhflkajsdhflkajsdhflkajsdhf
asjkdh 

Output

7
16
0
9
478

数据规模及约定

记$N_S$和$N_T$分别为字符串$S$和$T$的长度。
对于所有测试点：$K \le 5$
测试点1-2：$N_S \le 100, \quad N_T \le 50$
测试点3-4：$N_S \le 600, \quad N_T \le 50$
测试点5-6：$N_S \le 4000, \quad N_T \le 100$
测试点7-10:$N_S \le 10^5, \quad N_T \le 100$
时间限制1s，空间限制64MB。