子串

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

      对于一个字符串变量,例如"abcdefghijkl",它的子串就是像"cdefg"这样可以从中找到的连续的字符串。给定一个字符串和它的一个子串,求出这个子串在原串中不重叠得出现了几次。例如:原串为:aaaa 子串为:aa。那么子串在原串中出现了两次。

Input

输入数据的第一行为一个整数 T(0 < T < 20)
接下来 T 行每行为两个空格分隔的字符串,分别代表原串和子串(原串长度不超过100,子串长度不超过10)。

Output

对于每组测试数据,按照题目描述输出对应的结果。

Sample Input

2
aaaa aa
apapapapapapa pa

Sample Output

2
6

Hint

 

Source

qinchuan