给定一个长度为 $n$ 的字符串 $S=s_1s_2…s_n$ 以及一个长度为 $m$ 的字符串 $T=t_1t_2…t_m$。
两个字符串都由小写字母构成。
用 $s[l,r]$ 来表示字符串 $S$ 的子串 $s_ls_{l+1}…s_r$。
有 $q$ 个询问，每个询问给出两个整数 $l_i,r_i\ (1≤l_i≤r_i≤n)$，请你计算字符串 $T$ 在 $s[l_i,r_i]$ 中作为子串出现了多少次。
例如，字符串 $\text{abacabad}$ 中共包含 $4$ 个子串 $\text{ba}$，所以 $\text{ba}$ 在 $\text{abacabad}$ 中作为子串出现了 $4$ 次。

第一行包含三个整数 $n,m,q$。
第二行包含一个长度为 $n$ 的由小写字母构成的字符串 $S$。
第三行包含一个长度为 $m$ 的由小写字母构成的字符串 $T$。
接下来 $q$ 行，每行包含两个整数 $l_i,r_i$。

每个询问输出一行答案，一个整数，表示出现次数。

前三个测试点满足 $1≤n,m,q≤20$。
所有测试点满足 $1≤n,m≤1000,\ 1≤q≤10^5,\ 1≤l_i≤r_i≤n$。