| 问题描述 |
|---|
TQL在做生物实验时发现，一种名叫线性袋鼠的生物是单性繁殖生物，在繁殖后代时有可能会在某处产生变异，变异规则如下：遗传基因可以看成一个字符串c，变异因子可以看成另一个字符串a，如果c中的某处有子串a，那么这就是一个可能产生变异的位置；因为后代不至于变化太大，所以有且仅有一个位置产生变异。TQL想要知道这只袋鼠到底有几个位置有可能产生变异。 例如遗传基因c="ABCABCD"，变异因子a="AB"，因为c中有两个位置的子串等于a，故答案是2。 |
| 输入描述 |
多组案例。一个正整数T，表示案例的数量。（T<=100） 每组案例中由2个字符串c、a组成，其中c表示袋鼠的遗传基因，a表示变异因子。（c的长度不大于1e6，a的长度不大于1e5，a的长度不大于c的长度） |
| 输出描述 |
针对每组案例，输出一个整数，表示可能产生变异的位置数量。 每组案例输出完要换行。 |
| 样例输入复制样例 |
3 ABCABCD AB DABABCD AD AAAAAAA AA |
| 样例输出 |
2 0 6 |
| 相关 |