'''
寻寻觅觅
时间限制：C/C++语言 1000MS；其他语言 3000MS
内存限制：C/C++语言 65536KB；其他语言 589824KB
题目描述：
姆巴特是一名现役特种兵，他马上就要去参加特种兵大赛。
特种兵大赛不仅对体能体格有很高的要求，还需要选手具备超强的智力和反应力。
为了训练姆巴特的反应力和临场动脑能力，教练写了一串很长的文字A，还写了一串文字B，
训练总共Q次，每次教练会告诉姆巴特两个数字l和r，
姆巴特需要快速找出B在A[l..r]中出现了几次，
A[l..r]表示从A的A[l]开始长度为r-l+1的子串。
'''


'''
input
第一行一个字符串A。

第二行一个字符串B。两个字符串保证均只含小写字母。（1≤|A|≤500000, 1≤|B|≤100）

第三行一个正整数Q，表示训练次数。（1≤Q≤100000）

接下来m行每行两个整数l和r，表示一段区间。（1≤l≤r≤|A|）

output
共Q行，每行一个非负整数，表示出现的次数。
'''

'''
样例输入
comeonmandontconconnect
on
5
1 5
1 6
1 23
11 16
11 23


样例输出
0
1
4
2
3
'''
