Description

注：easy版本和hard版本本质是不同的问题，无法直接用hard版本的解法通过easy版本。

实际上，小任的初高中时期很喜欢在上课的时候说废话，因此惹恼了很多老师。有一天其中一个老师实在无法忍受小任的不良行为，准备审问小任。

老师对小任很是熟悉，他把所有小任会说的废话整理成了长度为 $m$ 一个字符串 $t$。小任料到老师会来审问自己，所以将自己一天所有说过的话整理成了长度为 $n$ 字符串 $s$。

老师一共会审问小任 $q$ 次，每次他将会给字符串 $t$ 的一个从下标 $l$ 开始到下标 $r$ 结束的连续子串（字符串 $t$ 的下标从 $1$ 开始），小任则需要精确得说出自己在今天一共说了几次这样的话（即询问的子串在 $s$ 中一共出现了几次）。

情况很危险，赶紧写一个程序帮帮小任吧！！

Format

Input

第一行给出三个正整数 $n,m,q$，其中 $1\leq n,m,q \leq 300$，分别表示字符串 $s$ 的长度，字符串 $t$ 的长度和老师询问的次数。

第二行给出一个长度为 $n$ 的均由小写字母组成的字符串 $s$，表示小任整理出来的字符串。

第三行给出一个长度为 $m$ 的均由小写字母组成的字符串 $t$, 表示老师整理出来的字符串。

接下来 $q$ 行每行包含两个整数 $l,r$，其中 $1\leq l \leq r \leq m$，表示老师询问的子串在字符串 $t$ 中的下标范围。

Output

一共输出 $q$ 行，每行输出一个整数，表示询问子串在字符串 $s$ 中出现的次数。

Samples

5 5 3
ababa
daaba
1 1
2 2
3 5

0
3
2

Note

对于第一次询问，老师查询的字符串为 "d"，在 $s$ 中并未出现，所以答案是 $0$。

对于第二次询问，老师查询的字符串为 "a"，在 $s$ 中出现 $3$ 次，

在 $s$ 的第 $1$ 个位置出现： $\textbf{a}baba$

在 $s$ 的第 $3$ 个位置出现： $abab \textbf{a}$

在 $s$ 的第 $5$ 个位置出现： $ab \textbf{a}ba$

所以答案是 $3$。

对于第三次询问，老师查询的字符串为 "aba"，在 $s$ 中出现 $2$ 次，

在 $s$ 的第 $1$ 个位置出现: $\textbf{aba}ba$

在 $s$ 的第 $3$ 个位置出现: $ab \textbf{aba}$

所以答案是 $2$。

Limitation

4s, 1024KiB for each test case.