题目描述

输入两个字符串\(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。