Logo Universal Online Judge

UOJ

时间限制:1 s 空间限制:512 MB
Statistics

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