KMP算法实现，能够实现字符串匹配。

输入

第一行一个整数N，表示测试数据组数。



接下来的N*2行，每两行表示一个测试数据。在每一个测试数据中，第一行为模式串，由不超过10^4个大写字母组成，第二行为原串，由不超过10^6个大写字母组成。



其中N< 20



输出

对于每一个测试数据，按照它们在输入中出现的顺序输出一行Ans，表示模式串在原串中出现的次数。-KMP algorithm, to achieve string matching.

nput

The first line is an integer N, indicating the number of test data sets.

The next N*2 lines, each of the two lines that a test data. In each test data, the first behavior pattern string, by no more than 10^4 capital letters, second behavior of the original string, by no more than 10^6 capital letters.

Among them N< 20

output

For each test data, in accordance with the order in which they appear in the input line Ans, the number of times that the pattern string appears in the original string.