题目描述

有两个由小写英文字母组成的字符串 $\red{s,t}$。 $\red{s}$的子串 $\red{s[l...r]}$为$\red{s_l,s_{l+1}...s_r }$不改变顺序组成的字符串。

字符串$\red{a }$在字符串$\red{b }$中出现的次数为满足 $\red{b[i...i+|a|-1]=a}$的 $\red{i(1<=i<=|b|-|a|+1)}$的个数。

由 $\red{q}$个询问，第$\red{i }$个询问给定两个整数$\red{l_i,r_i,，}$问 在 $\red{s[l_i...r_i] }$中出现的次数。

输入格式

第一行三个整数 $\red{|s|,|t|,q}$ ，$\red{s }$的长度， $\red{t}$的长度，询问数。

接下里 $\red{q}$行，每行两个整数 $\red{l_i,r_i}$

输出格式

$\red{q}$行，每行一个整数。

样例

输入样例1

15 2 3 

abacabadabacaba 

ba

1 15 

3 4 

2 14

输出样例1

4

0

3

输入样例2

3 5 2 

aaa 

baaab 

1 3 

1 1

输出样例2

0

0

提示

对于$\red{100\%}$的数据满足, $\red{1<=n,m,q<=100}$

对于$\red{100\%}$的数据满足, $\red{1<=n,m<=10^3,1<=q<=10^5,1<=l_i<=r_i<=n}$