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.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;


public class Main {
    public static void main(String[] args) {
        new Main().run();
    }


	private IO io = new IO();
	private String text;
	private String pattern;
	private int[] pos = new int[10000];
	private int numPos = 0;


	private void run() {
		// Trash
		io.readLine();
		io.getInteger();
		io.getInteger();
		//
		int casos = io.getInteger();
		text = io.readLine();
		pattern = io.readLine();
		int pl = pattern.length();

		// Fill pos
		int i = 0;
		while (i >= 0) {
			i = text.indexOf(pattern, i);
			if (i >= 0) {
				pos[numPos++] = i++;
			}
		}

		// Rangos de búsqueda {l,r)
		for (int c = 0; c < casos; c++) {
			io.readLine();
			int l = io.getInteger() - 1;
			int r = io.getInteger() - 1;
			int cont = 0;
			if (r - l + 1 >= pl) {
				for (i = 0; i < numPos; i++) {
					if ((pos[i] >= l) && (pos[i] + pl - 1 <= r)) {
						cont++;
					} else {
						if (cont > 0) {
							break;
						}
					}
				}
			}
			io.println(cont);
		}
	}


    public class IO {
        private final BufferedReader in;
        private final PrintWriter out;
        private String[] tokens;
        private int currentToken;


        public IO() {
            tokens = new String[0];
            currentToken = 0;
            in = new BufferedReader(new InputStreamReader(System.in));
            out = new PrintWriter(System.out);
        }


        public int getNumItems() {
            return tokens.length;
        }

        public String getString() {
            if (currentToken >= tokens.length) { return null; }
            return tokens[currentToken++];
        }

        public int getInteger() {
            String s = getString();
            int n;
            try { n = Integer.parseInt(s); } catch (NumberFormatException e) { n = 0; }
            return n;
        }


        public long getLong() {
            String s = getString();
            long n;
            try { n = Long.parseLong(s); } catch (NumberFormatException e) { n = 0; }
            return n;
        }

        public double getDouble() {
            String s = getString();
            double r;
            try { r = Double.parseDouble(s); } catch (NumberFormatException e) { r = 0.0; }
            return r;
        }


        public int[] getIntegerArray() {
            int l = getNumItems();
            int[] v = new int[l];
            for (int i = 0; i < l; i++) {
                v[i] = getInteger();
            }
            return v;
        }


		public long[] getLongArray() {
			int l = getNumItems();
			long[] v = new long[l];
			for (int i = 0; i < l; i++) {
				v[i] = getLong();
			}
			return v;
		}


        public void print(Object o) {
            out.print(o);
            out.flush();
        }

        public void println(Object o) {
            print(o); out.println(); out.flush();
        }


        public String readLine() {
            String s = "";
            try {
                s = in.readLine();
                tokens = s.split(" ");
            } catch (Exception e) {
                tokens = new String[0];
            }
            currentToken = 0;
            return s;
        }

    }


}
