You are given two strings $s$ and $t$, both consisting only of lowercase Latin letters.

The substring $s[l..r]$ is the string which is obtained by taking characters $s_l, s_{l + 1}, \dots, s_r$ without changing the order.

Each of the occurrences of string $a$ in a string $b$ is a position $i$ ($1 \le i \le |b| - |a| + 1$) such that $b[i..i + |a| - 1] = a$ ($|a|$ is the length of string $a$).

You are asked $q$ queries: for the $i$-th query you are required to calculate the number of occurrences of string $t$ in a substring $s[l_i..r_i]$.


-----Input-----

The first line contains three integer numbers $n$, $m$ and $q$ ($1 \le n, m \le 10^3$, $1 \le q \le 10^5$) — the length of string $s$, the length of string $t$ and the number of queries, respectively.

The second line is a string $s$ ($|s| = n$), consisting only of lowercase Latin letters.

The third line is a string $t$ ($|t| = m$), consisting only of lowercase Latin letters.

Each of the next $q$ lines contains two integer numbers $l_i$ and $r_i$ ($1 \le l_i \le r_i \le n$) — the arguments for the $i$-th query.


-----Output-----

Print $q$ lines — the $i$-th line should contain the answer to the $i$-th query, that is the number of occurrences of string $t$ in a substring $s[l_i..r_i]$.


-----Examples-----
Input
10 3 4
codeforces
for
1 3
3 10
5 6
5 7

Output
0
1
0
1

Input
15 2 3
abacabadabacaba
ba
1 15
3 4
2 14

Output
4
0
3

Input
3 5 2
aaa
baaab
1 3
1 1

Output
0
0



-----Note-----

In the first example the queries are substrings: "cod", "deforces", "fo" and "for", respectively.

Difficulty: interview

Starter code:

Solutions:
#      
import collections, atexit, math, sys, bisect 

sys.setrecursionlimit(1000000)
def getIntList():
    return list(map(int, input().split()))    

try :
    #raise ModuleNotFoundError
    import numpy
    def dprint(*args, **kwargs):
        print(*args, **kwargs, file=sys.stderr)
    dprint('debug mode')
except ModuleNotFoundError:
    def dprint(*args, **kwargs):
        pass



inId = 0
outId = 0
if inId>0:
    dprint('use input', inId)
    sys.stdin = open('input'+ str(inId) + '.txt', 'r') #标准输出重定向至文件
if outId>0:
    dprint('use output', outId)
    sys.stdout = open('stdout'+ str(outId) + '.txt', 'w') #标准输出重定向至文件
    atexit.register(lambda :sys.stdout.close())     #idle 中不会执行 atexit
    
N, M, Q = getIntList()

s1 = input()
s2 = input()

tot = 0
zt = [0]

for i in range(N):
    if s1[i:i+M] == s2:
        tot+=1
    zt.append(tot)
dprint(zt)
for i in range(Q):
    a,b = getIntList()
    b0 = b- M+1
    if b0<a:
        print(0)
    else:
        print(zt[b0] - zt[a-1])









n,m,q = list(map(int,input().split()))
s = input()
t = input()
l = []
r = []
for i in range(n-m+1):
    if s[i:i+m] == t:
        l.append(i)
        r.append(i+m-1)
for i in range(q):
    x,y = list(map(int,input().split()))
    x-=1
    y-=1
    ans = 0
    for j in range(len(l)):
        if x <= l[j] and y >= r[j]:
            ans+=1
    print(ans)


import re, bisect

n, m, q = [int(v) for v in input().split()]
s = input().strip()
t = input().strip()

starts = [m.start() for m in re.finditer('(?=%s)' % t, s)]

for _ in range(q):
    l, r = [int(v) for v in input().split()]
    if r - l + 1 < len(t):
        print(0)
    else:
        print(bisect.bisect_right(starts, r - len(t)) - bisect.bisect_left(starts, l - 1))


n, m, q = [int(i) for i in input().split()]
s = list(input())
t = list(input())
lt = len(t)
ls = len(s)
start = []
for i in range(ls - lt +1):
    j = i
    count = 0
    while s[j] == t[count]:
        j += 1
        count += 1
        if count >= lt:
            break
    if count == lt:
        start.append(i + 1)

start += [n + 1]
for i in range(q):
    l, r = [int(j) for j in input().split()]
    r -= lt - 1
    if l > r:
        print(0)
        continue
    f = False
    for j in range(len(start)):
        if (f == False) and (start[j] >= l):
            f = True
            begin = j
        if (f) and (start[j] > r):
            end = j
            break
    print(end - begin)




import sys
import io

stream_enable = 0

inpstream = """
15 2 3
abacabadabacaba
ba
1 15
3 4
2 14
"""

if stream_enable:
    sys.stdin = io.StringIO(inpstream)
    input()

def inpmap():
    return list(map(int, input().split()))

n, m, q = inpmap()
a = input()
b = input()
s = [0] * n
s[0] = int(a.startswith(b))
for i in range(1, n):
    s[i] = s[i - 1] + int(a[i:i+m] == b)
for i in range(q):
    x, y = inpmap()
    r = (s[y - m] if y - m >= 0 else 0) - (s[x - 2] if x - 2 >= 0 else 0)
    print(max(r, 0))



n,m,q=list(map(int,input().split()))
s=str(input())
t=str(input())
arrx=[]
i=0
count=0
while(i<n):
    if(s[i]==t[0]):
        j=0
        while(j+i<n and j<m and s[j+i]==t[j]):
            j+=1
        if(j==len(t)):
            count+=1
    arrx.append(count)
    i+=1
for i in range(q):
    x,y=list(map(int,input().split()))
    if(y-x<m-1):
        print(0)
    else:
        if(x==1):
            print(arrx[y-m])
        else:
            print(arrx[y-m]-arrx[x-2])


from sys import stdin
from math import *

line = stdin.readline().rstrip().split()
n = int(line[0])
m = int(line[1])
q = int(line[2])

s = stdin.readline().rstrip().split()[0]
t = stdin.readline().rstrip().split()[0]

bools = [0] * (n - m + 1 + 1)

accum = 0
for i in range(n - m, -1, -1):
    if s[i:i+m] == t:
        accum += 1
    bools[i] = accum

for i in range(q):
    numbers = list(map(int, stdin.readline().rstrip().split()))
    l = numbers[0] - 1
    r = numbers[1] - 1 - m + 1 + 1
    if r > l:
        print(bools[l] - bools[r])
    else:
        print(0)
 #suma = 0
#    for j in range(l, r+1):
#        if bools[j]:
#            suma += 1




n, m, q = list(map(int, input().split()))
s = list(input())
t = list(input())
a = [list(map(int, input().split())) for i in range(q)]

if n < m:
    for i in range(q):
        print(0)
    return

res = [0] * (n - m + 1)
for i in range(n - m + 1):
    if s[i:(i + m)] == t:
        res[i] = 1

for u in range(q):
    l = a[u][0]
    r = a[u][1]

    ans = 0
    for y in range(l - 1, r - m + 1):
        # print(y)
        if res[y] == 1:
            ans += 1

    print(ans)

n, m, q = map(int, input().split())
s = input()
t = input()
arr = []
for i in range(n - m + 1):
    if s[i:i + m] == t:
        arr.append(i)
for i in range(q):
    l, r = map(int, input().split())
    k = 0
    for j in range(len(arr)):
        if arr[j] >= l - 1 and arr[j] + m - 1<= r - 1:
            k = k + 1
    print(k)

n, m, q = list(map(int, input().split()))
s = input()
t = input()
arr = [0] * n
for i in range(n - m + 1):
    if t == s[i:i+m]:
        arr[i] = 1
    if i: arr[i] += arr[i - 1]
for i in range(q):
    l, r = list(map(int, input().split()))
    l -= 1
    r -= 1
    L = l - 1
    R = r - m + 1
    if R < L: 
        print(0)
        continue
    if L >= 0: 
        print(arr[R] - arr[L])
    else:
        print(arr[R])


#list_int 並べて出力 print (' '.join(map(str,ans_li)))
#list_str 並べて出力 print (' '.join(list))

# 2進数 format(10, 'b') # '1010'

''' 二次元配列を一列ずつ
for i in ans:
	print(*i)
'''
''' heapq
queue = []
heapq.heapify(queue) #heapqの作成
heapq.heappush(queue,num) #numのpush(値の追加)
pop = heapq.heappop(queue) #numのpop(最小値の出力)
pop = heapq.heappushpop(queue,num) #push -> pop

'''

from collections import defaultdict
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
AtoZ = [chr(i) for i in range(65,65+26)]
atoz = [chr(i) for i in range(97,97+26)]

def inpl(): return list(map(int, input().split()))
def inpl_str(): return list(input().split())

N,M,q = inpl()
S = input()
T = input()
azu = [0]*(N-M+1)
qq = []

for i in range(q):
	qq.append(inpl())

if M > N:
	for i in range(q):
		print(0)
	return

for i in range(0,N-M+1):
	if S[i:i+M] == T:
		azu[i] = 1

SUM = 0
nyan = [0]
for az in azu:
	SUM += az
	nyan.append(SUM)


for l,r in qq:
	l -= 1
	if r - l < M:
		print(0)
	else:
		print(nyan[r-M+1] - nyan[l])


import sys


def main():
    n, m, q = list(map(int, input().strip().split()))
    s = input()
    t = input()

    pos = []
    for i in range(len(s)):

        if i + len(t) <= len(s) and s[i:i+len(t)] == t:
            pos.append(1)
        else:
            pos.append(0)

    sum = [0]
    for i in range(len(pos)):
        sum.append(sum[-1] + pos[i])

    for _ in range(q):
        l, r = list(map(int, input().strip().split()))
        r = r - len(t) + 1
        l -= 1

        if l < r:
            print(sum[r] - sum[l])
        else:
            print(0)

    return 0


def test(i):
    with open("test_{}.txt".format(i)) as fin:
        sys.stdin = fin
        main()


def __starting_point():
    # test(1)
    # test(2)
    return(main())

__starting_point()

n,m, q = list(map(int, input().split()))
s = str(input())
t = str(input())

def is_in(index):
    if index + m > n:
        return False
    
    for j in range(m):
        if not t[j] == s[index + j]:
            return False
    return True
        
precalc_ar_2 = [0 for  i in range(n  +1)]
in_was = [ False for i in range(n)]

for i in range(n):
    if is_in(i):
        in_was[i] = True


val = 0
for i in range(1, n + 1):
    if in_was[i - 1]:
        val +=1
    precalc_ar_2[i] = val        


for i in range(q):
    l, r = list(map(int,input().split()))
    if r- m + 1 < 0 or r- m + 1 < l  - 1:
        print(0)
    else:
        print(precalc_ar_2[r - m +1] - precalc_ar_2[l - 1])


3

def calc(l, r, layers, li):
    if r - l == 1:
        return layers[li][l]

    xl = l
    if l % 2 == 1:
        xl -= 1
    xr = r
    if r % 2 == 1:
        xr += 1

    ans = calc(xl // 2, xr // 2, layers, li + 1)
    if xl != l:
        ans -= layers[li][xl]
    if xr != r:
        ans -= layers[li][xr - 1]
    return ans


def solve(N, M, Q, S, T, A):
    base = [0] * N
    i = 0
    while True:
        try:
            i = S.index(T, i)
            base[i] = 1
            i += 1
        except ValueError:
            break

    layers = [base]
    while len(layers[-1]) > 1:
        prev = layers[-1]
        if len(prev) % 2 == 1:
            prev.append(0)

        layer = []
        for i in range(len(prev) // 2):
            layer.append(prev[2 * i] + prev[2 * i + 1])

        layers.append(layer)

    ans = []
    for (l, r) in A:
        l -= 1

        r -= M - 1
        if r <= l:
            ans.append(0)
            continue

        ans.append(calc(l, r, layers, 0))

    return ans


def main():
    N, M, Q = [int(e) for e in input().split(' ')]
    S = input()
    T = input()
    A = [map(int, input().split(' ')) for _ in range(Q)]

    assert len(S) == N
    assert len(T) == M

    print(*solve(N, M, Q, S, T, A), sep='\n')


def __starting_point():
    main()

__starting_point()

import sys

n,m,q=list(map(int,input().split()))
s=input()
t=input()
A=[None]*q
for i in range(q):
    A[i]=list(map(int,input().split()))

if m>n:
    for i in range(q):
        print(0)

    return

score=[0 for i in range(n-m+1)]
for i in range(n-m+1):
    if t==s[i:i+m]:
        score[i]=1

SUM=[0 for i in range(n-m+1)]
SUM[0]=score[0]
for i in range(1,n-m+1):
    SUM[i]=score[i]+SUM[i-1]


SUM=[0]+SUM
for i in range(q):
    if A[i][1]-m+1<=A[i][0]-1:
        print(0)
    else:
        print(SUM[A[i][1]-m+1]-SUM[A[i][0]-1])


# from math import ceil
#from sys import stdout

t = 1#int(input())
for test in range(1,t+1):
    n,m,q = list(map(int, input().split()))
    s = input()
    t = input()
    indices = [0 for i in range(n)]
    for i in range(n):
        tmp = s.find(t, i)
        if tmp==-1:
            break
        else:
            indices[tmp] = 1
    pref = [0]
    for i in indices:
        pref.append(i+pref[-1])
    for i in range(q):
        l,r = list(map(int, input().split()))
        if r-l+1<m:
            print(0)
            continue
        print(pref[r-m+1]-pref[l-1])

        




    














    


n, m, q = list(map(int, input().split()))
a = input()
b = input()
c = [0]
for i in range(1, n + 1):
    # print(a[max(i - m, 0):i])
    c.append(c[i - 1] + (a[max(i - m, 0):i] == b))

# print(c)
for i in range(q):
    l, r = list(map(int, input().split()))
    if r - l >= m - 1:
        print(max(c[r] - c[l + m - 2], 0))
    else:
        print(0)


def coun(s, t):
    d = 0
    for i in range(len(s) - len(t) + 1):
        if s[i:i + len(t)] == t:
            d += 1
    return(d)

n, m, q = list(map(int, input().split()))
s = input()
t = input()
x = [0]

for j in range(n):
    x.append(coun(s[:j + 1], t))
for i in range(q):
    l, r = list(map(int, input().split()))
    r += 1
    if m <= r - l:
        print(x[r - 1] - x[max(0, l + m - 2)])
    else:
        print(0)


# n=int(input())
# ns=[int(x) for x in input().split()]
# dp=[None]*n
# def greater(i,num):
#     return ns[i]+ns[i+1]>=num
# def biSearch(t,l,r):
#     if r-l<=1:
#         return l
#     m=(l+r)//2
#     if greater(m,t)
#
#
# def update(t):
#     l=ns[t]
n,m,q=[int(x)for x in input().split()]
sn=input()
sm=input()


def eq(i):
    for j in range(m):
        if sn[i+j]!=sm[j]:
            return False
    return True
re=[0]*n
for i in range(n-m+1):
    if eq(i):
        re[i]=1
for i in range(1,n):
    re[i]+=re[i-1]

for i in range(q):
    l,r=[int(x)-1 for x in input().split()]
    if r-l+1<m:
        print(0)
        continue
    if l==0:
        print(re[r-m+1])
    else:
        print(re[r-m+1]-re[l-1])

N,M,Q = [int(x) for x in input().split()]
S = input() #length N
T = input() #length M
A = []
pref = []
for i in range(N):
  A.append(0)
  pref.append(0)
for i in range(N):
  if S[i:i+M] == T:
    A[i] = 1
  if i > 0:
    pref[i] = pref[i-1] + A[i]
  else:
    pref[i] = A[i]
for i in range(Q):
  l,r = [int(x) for x in input().split()]
  l -= 1
  r -= 1
  if r-l+1 >= M:
    if r-M+1 >= 0:
      if l-1>=0:
        print(pref[r-M+1]-pref[l-1])
      else:
        print(pref[r-M+1])
    else:
      print(0)
  else:
    print(0)

n,m,q=list(map(int,input().split()))
s=input()
t=input()
tt=[0]*1111
for i in range(n-m+1):
    j=0
    while j<m and s[i+j]==t[j]: j+=1
    if j>=m: tt[i+1]=1
for i in range(1,n+1): tt[i]+=tt[i-1]
for i in range(q):
    a,b=list(map(int,input().split()))
    if b-a+1<m:
        print(0)
        continue
    print(tt[b-m+1]-tt[a-1])





'''
////////////////      //////        ///////      //             ///////     //  //   //
////          //    ///   ///     ///    ///     //            ///  ///     ////     //
////    ////       ///     ///   ///      ///    //           /////////     ////     ///////
////     /////    ///       /// ///        ///   //          ///    ///     ////     //   //
//////////////     ///////////   ///////////     //////     ///     ///     //  //   //   //
'''



'''input
3 5 2
aaa
baaab
1 3
1 1
'''
from bisect import bisect_left, bisect_right

n, m, q = list(map(int, input().split()))
s, t = input(), input()
x = []
for i in range(len(s) - len(t) + 1):
	if s[i:i+len(t)] == t:
		x.append(i)
sx = set(x)
for _ in range(q):
	l, r = list(map(int, input().split()))
	if r - l + 1 < len(t):
		print(0)
		continue
	i = bisect_right(x, l - 1)
	j = bisect_left(x, r - len(t))
	if l - 1 in sx:
		i -= 1
	if r - len(t) not in sx:
		j -= 1
	print(j - i + 1)





from bisect import bisect_left, bisect_right
   
def main():
    n, m, q = list(map(int, input().split(' ')))
    s = input()
    t = input()

    ps = []
    for i in range(n-m+1):
        if t == s[i:i+m]:
            ps.append(i)
    
    ans = []
    for _ in range(q):
        l, r = list(map(int, input().split(' ')))
        l, r = l - 1, r - 1
        i = bisect_left(ps, l)
        j = bisect_right(ps, r - m + 1)
        ans.append(max(j - i, 0))
    for x in ans:
        print(x)

def __starting_point():
    main()

__starting_point()


def mi():
	return list(map(int, input().split()))

n,m,q = mi()
s = list(input())
t = list(input())
pre1 = [0]*n
pre2 = [0]*n
if n>=m:
	for i in range(n-m+1):
		if (s[i:i+m]==t):
			pre1[i+m-1] = 1
			pre2[i] = 1
	for i in range(1,n):
		pre1[i]+=pre1[i-1]
		pre2[i]+=pre2[i-1]
pre1.insert(0,0)
pre2.insert(0,0)


while q:
	q-=1
	l,r = mi()
	s1, s2 = 0,0
	#for i in range(l, r+1):
		#s1+=pre1[i]
		#s2+=pre2[i]
	if m>n:
		print(0)
		continue
	if r<m or r-l+1<m or n-l+1<m:
		print(0)
		continue
	s1 = pre1[r]-pre1[l-1+m-1]
	s2 = pre2[r-m+1]-pre2[l-1]
	if s1>0 and s2>0:
		print(min(s1,s2))
	else:
		print(0)