改(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