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}, ..., s_r without changing the order.

Each of the occurrences of string a in a string b is a position i (1 ≤ i ≤ |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 ≤ n, m ≤ 10^3, 1 ≤ q ≤ 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 ≤ l_i ≤ r_i ≤ 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.

import java.util.*;
import java.io.*;
import java.math.*;
public class loser
{
    static class InputReader {
        public BufferedReader br;
        public StringTokenizer token;
        public InputReader(InputStream stream)
        {
            br=new BufferedReader(new InputStreamReader(stream),32768);
            token=null;
        }

        public String next()
        {
            while(token==null || !token.hasMoreTokens())
            {
                try
                {
                    token=new StringTokenizer(br.readLine());
                }
                catch(IOException e)
                {
                    throw new RuntimeException(e);
                }
            }
            return token.nextToken();
        }

        public int nextInt()
        {
            return Integer.parseInt(next());
        }

        public long nextLong()
        {
            return Long.parseLong(next());
        }
    }
    static class card{
        String s;
        int l;
        public card(String s,int i)
        {
            this.s=s;
            this.l=i;
        }
    }
    static class sort implements Comparator<card>
    {
        public int compare(card o1,card o2)
        {
            if(o1.l!=o2.l)
                return (o1.l-o2.l);
            else
                return o1.s.compareTo(o2.s);
        }
    }
    static void shuffle(int a[])
    {
        List<Integer> l=new ArrayList<>();
        for(int i=0;i<a.length;i++)
            l.add(a[i]);
        Collections.shuffle(l);
        for(int i=0;i<a.length;i++)
            a[i]=l.get(i);
    }

    /*static long gcd(long a,long b)
    {
    if(b==0)
    return a;
    else
    return gcd(b,a%b);
    }
    static boolean valid(int i,int j,int r,int c)
    {
    if(i<r && i>=0 && j<c && j>=0)
    return true;
    else
    return false;
    }*/
    static class Pair
    {
        int a;int b;
        public Pair(int a,int b)
        {
            this.a =a;
            this.b =b;
        }
    }
    static boolean beauty(int n)
    {
        String s1=Integer.toBinaryString(n);
        int f=1,o=0,z=0;boolean res=true;
        for(int i=0;i<s1.length();i++)
        {
            if(f==1 && s1.charAt(i)=='1')
                o++;
            else if(s1.charAt(i)=='0' && f==1)
            {
                z++;
                f=0;
            }
            else if(s1.charAt(i)=='0' && f==0)
                z++;
            else if(f==0 && s1.charAt(i)=='1')
            {
                res=false;
                break;
            }
        }
        if((o-1)!=z)
            res=false;
        return res;
    }

    public  static void main(String[] args) 
    {
        InputReader sc=new InputReader(System.in);
        int n=sc.nextInt();
        int m=sc.nextInt();
        int q=sc.nextInt();
        String s=sc.next();
        String t=sc.next();
        if(m>n)
        {
            for(int i=0;i<q;i++)
            {
                int l=sc.nextInt();
                int r=sc.nextInt();
                System.out.println(0);
            }
        }
        else
        {
            int b[]=new int[n];
            for(int i=0;i<=n-m;i++)
            {
                if( s.substring(i,i+m).equals(t))
                {
                    b[i]=1;
                }
            }
            for(int i=0;i<q;i++)
            {
                int l=sc.nextInt();
                int r=sc.nextInt();
                if((r-l+1)>=m)
                {
                    int ans=0;
                    for(int j=l-1;j<=r-m;j++)
                    {
                        if(b[j]==1)
                        ans++;
                    }
                    System.out.println(ans);
                }
                else
                System.out.println(0);
            }
        }
    }
}