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.io.*;
import java.math.BigInteger;
import java.util.*;

public class Main implements Runnable {

    int maxn = (int)1e5+111;
    int n,m,k;
    long a[] = new long[maxn];

    void solve() throws Exception {
        int n = in.nextInt();
        int m = in.nextInt();
        int q = in.nextInt();

        String s = in.nextToken();
        String t = in.nextToken();
        String forkmp = t+"#"+s;
        int kmp[] = buildPrefix(forkmp.toCharArray());

        int prefSum[] = new int[maxn];
        for (int i=m; i<kmp.length; i++) {
            if (kmp[i]==m) {
                prefSum[i] = prefSum[i-1] + 1;
            } else {
                prefSum[i] = prefSum[i-1];
            }
        }

        int val = m+1;
        for (int i=1; i<=q; i++) {
            int left = in.nextInt() - 1 + val + (m-2);
            int right = in.nextInt() - 1 + val;
            if (right>=left) {
                out.println(prefSum[right]-prefSum[left]);
            } else {
                out.println(0);
            }
        }
    }

    public int[] buildPrefix(char c[]) {
        int arr[] = new int[c.length];
        for (int i=1; i<c.length; i++) {
            int j = arr[i-1];
            while (j>0 && c[i]!=c[j]) {
                j = arr[j-1];
            }
            if (c[i]==c[j]) j++;
            arr[i] = j;
        }
        return arr;
    }

    class Pair {
        int x, y;

        public Pair(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    String fileInName = "";

    boolean file = false;
    boolean isAcmp = false;

    static Throwable throwable;
    public static void main (String [] args) throws Throwable {
        Thread thread = new Thread(null, new Main(), "", (1 << 26));
        thread.start();
        thread.join();
        thread.run();
        if (throwable != null)
            throw throwable;
    }

    FastReader in;
    PrintWriter out;

    public void run() {
        String fileIn = "absum.in";
        String fileOut = "absum.out";

        try {
            if (isAcmp) {
                if (file) {
                    in = new FastReader(new BufferedReader(new FileReader(fileIn)));
                    out = new PrintWriter (fileOut);
                } else {
                    in = new FastReader(new BufferedReader(new InputStreamReader(System.in)));
                    out = new PrintWriter(System.out);
                }
            } else if (file) {
                in = new FastReader(new BufferedReader(new FileReader(fileInName+".in")));
                out = new PrintWriter (fileInName + ".out");
            } else {
                in = new FastReader(new BufferedReader(new InputStreamReader(System.in)));
                out = new PrintWriter(System.out);
            }

            solve();
        } catch(Exception e) {
            throwable = e;
        } finally {
            out.close();
        }

    }


}

class FastReader {
    BufferedReader bf;
    StringTokenizer tk = null;

    public FastReader(BufferedReader bf) {
        this.bf = bf;
    }

    public String nextToken () throws Exception {
        if (tk==null || !tk.hasMoreTokens()) {
            tk = new StringTokenizer(bf.readLine());
        }
        if (!tk.hasMoreTokens()) return nextToken();
        else
            return tk.nextToken();
    }

    public int nextInt() throws Exception {
        return Integer.parseInt(nextToken());
    }

    public long nextLong() throws Exception {
        return Long.parseLong(nextToken());
    }

    public double nextDouble() throws Exception {
        return Double.parseDouble(nextToken());
    }
}