1148:出现了几次

一个串的子串是指该串的一个连续的局部。如果不要求连续，则可称为它的子序列。比如对于串： "abcdefg" 而言，"ab"，"abd"，"aceg" 等都是它的子序列。现在给你两个字符串A、B，请问B在A中作为子序列出现了多少次。特别地，字符串A中的任一字符最多只能贡献一次。怕你们看不懂题目，所以这次多加了几组测试样例^^。

第一行是一个正整数n代表测试案例的数量。(1<=n<=20)

每组案例是两个不含空格的字符串A、B。

保证A、B的长度不会超过30。

B在A中作为子序列出现了多少次。

每组案例输出结束后都要换行。

5

abcabc acb

abcabc abc

aabbcc abc

ababa aba

aaaaa aa

1

2

2

1

2

在第三组测试案例中，你总共能从字符串A中找到两个字符串B。

在第四组测试案例中，aba出现在字符串下标为012(014)的位置上，由于每个字符最多只能贡献一次，因此我们认为下标为234的三个字符组成的aba是无效的。