Description

给出两个串S1，S2（只有大写字母），求S1在S2中出现的次数。
例如S1=“ABA”,S2=“ABABA”，答案为2。

Format

Input

第一行为一个整数T，表示共有T测试组数据。
接下来的共有2T行，第2i-1行（0<i<=T）为第i组测试数据的字串S1,第2i行表示第i组测试数据中的字串S2.
每组数据保证strlen(S1)<=10^4,strlen(S2)<=10^6。

Output

输出共T行，每行为一组字串匹配的结果。

Sample 1

Input

3
BAPC
BAPC
AZA
AZAZAZA
VERDI
AVERDXIVYERDIAN

Output

1
3
0

Limitation

1s, 64MiB for each test case.
字符串Hash（或KMP）模板题

Source

poj3461