改(transform)
你有两个字符串 $A$ 和 $B$。求 $A$ 的子串中，有多少存在一个子序列，可以由 $B$ 经过下列变换可以变为：
对于一个字符串，每次取出开头的字符，将其插入到一个初始为空的双端队列的开头或结尾，最后双端队列从左到右形成的串即为变换后的串。
输入格式
第一行一个整数 $T$，表示测试数据个数。 接下来每个测试数据： 第一行一个字符串，表示字符串 $A$。保证只有小写字母。 第二行一个字符串，表示字符串 $B$。保证只有小写字母。
输出格式
对于每个测试数据，输出一行一个整数，表示满足条件的子串数。
数据范围
| 测试点编号 | $\vert A \vert$ 的范围 | $\vert B\vert$ 的范围 |
|---|---|---|
| $1$ | $\le 1$ | $\le 1$ |
| $2\sim 3$ | $\le 10$ | $\le 10$ |
| $4\sim 5$ | $\le 64$ | $\le 10$ |
| $6\sim 8$ | $\le 128$ | $\le 64$ |
| $9\sim 12$ | $\le 256$ | $\le 128$ |
| $13\sim 14$ | $\le 2048$ | $\le 128$ |
| $15\sim 18$ | $\le 2048$ | $\le 1024$ |
| $19\sim 20$ | $\le 4096$ | $\le 2048$ |
对于所有数据，保证 $1\le T \le 8$。
样例
输入
5
abaa
ab
acabaca
abc
abbbbababababababbbabbabbbabbababbbabbabbbbabababbaaaababab
ababaaabb
abcdefghijklmnopqrstuvwxyz
pof
abababababababa
aaaaaaaaaaaa输出
5
12
1083
66
0