| 问题描述 |
|---|
对于两个字符串$$S$$和$$T$$，若$$T$$可以通过删除任意个字符变成$$S$$，那么我们就称$$T$$是$$S$$的子序列。 对于字符串$$\text{abcdefg}$$而言，$$\text{ac,de,adg}$$是它的子序列，但$$\text{ba,acb}$$不是它的子序列。 现在给出两个字符串$$S$$和$$T$$，请你编程输出$$T$$作为$$S$$的子序列出现了几次？ 注意：每在$$S$$中找到一个子序列$$T$$时，你可以认为需要从$$S$$中拿掉这个子序列。 如：在$$\text{abcadbca}$$中找子序列$$\text{aba}$$时，你最多只能找到$$1$$次，而不是$$2$$次。 |
| 输入描述 |
第一行是一个正整数$$n$$代表测试案例的数量。($$1 \leq n \leq 20$$) 每组案例包含两个不含空白符且长度不超过$$30$$的字符串$$S,T$$。 |
| 输出描述 |
针对每组案例，输出$$T$$作为$$S$$的子序列出现了几次。 |
| 样例输入复制样例 |
5 abcabc acb abcabc abc aabbcc abc ababa aba aaaaa aa |
| 样例输出 |
1 2 2 1 2 |
| 相关 |