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.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.List;
import java.util.InputMismatchException;
import java.io.IOException;
import java.io.InputStream;
import java.util.ArrayList;

/**
 * Built using CHelper plug-in Actual solution is at the top
 *
 * @author MaxHeap
 */
public class Main {

  public static void main(String[] args) {
    InputStream inputStream = System.in;
    OutputStream outputStream = System.out;
    InputReader in = new InputReader(inputStream);
    PrintWriter out = new PrintWriter(outputStream);
    TaskB solver = new TaskB();
    solver.solve(1, in, out);
    out.close();
  }

  static class TaskB {

    public void solve(int testNumber, InputReader in, PrintWriter out) {
      int n = in.nextInt();
      int m = in.nextInt();
      int q = in.nextInt();
      String s = in.next();
      String pat = in.next();

      List<Integer> ind = StringUtils.getIndexes(s, pat);

      int[] val = new int[ind.size()];
      int[] acc = new int[10000];
      for (int i = 0; i < val.length; i++) {
        val[i] = ind.get(i);
        acc[val[i] + 1]++;
        // acc[val[i] + 1 + pat.length()]--;
      }
      for (int i = 1; i < 10000; i++) {
        acc[i] += acc[i - 1];
      }

      while (q-- > 0) {
        int a = in.nextInt();
        int b = in.nextInt() - m + 1;
        if (a > b) {
          out.println(0);
          continue;
        }
        out.println(acc[b] - acc[a - 1]);
      }
    }

  }

  static class InputReader {

    private InputStream stream;
    private byte[] buf = new byte[1 << 13];
    private int curChar;
    private int numChars;

    public InputReader(InputStream stream) {
      this.stream = stream;
    }

    public int read() {
      if (this.numChars == -1) {
        throw new UnknownError();
      } else {
        if (this.curChar >= this.numChars) {
          this.curChar = 0;

          try {
            this.numChars = this.stream.read(this.buf);
          } catch (IOException ex) {
            throw new InputMismatchException();
          }

          if (this.numChars <= 0) {
            return -1;
          }
        }

        return this.buf[this.curChar++];
      }
    }

    public int nextInt() {
      int c;
      for (c = this.read(); isSpaceChar(c); c = this.read()) {
      }

      byte sgn = 1;
      if (c == 45) {
        sgn = -1;
        c = this.read();
      }

      int res = 0;

      while (c >= 48 && c <= 57) {
        res *= 10;
        res += c - 48;
        c = this.read();
        if (isSpaceChar(c)) {
          return res * sgn;
        }
      }

      throw new InputMismatchException();
    }

    public String next() {
      int c;
      while (isSpaceChar(c = this.read())) {
      }

      StringBuilder result = new StringBuilder();
      result.appendCodePoint(c);

      while (!isSpaceChar(c = this.read())) {
        result.appendCodePoint(c);
      }

      return result.toString();
    }

    public static boolean isSpaceChar(int c) {
      return c == 32 || c == 10 || c == 13 || c == 9 || c == -1;
    }

  }

  static class StringUtils {

    public static int[] prefixFunction(char[] s) {
      int[] p = new int[s.length];
      int k = 0;
      for (int i = 1; i < s.length; i++) {
        while (k > 0 && s[k] != s[i]) {
          k = p[k - 1];
        }
        if (s[i] == s[k]) {
          ++k;
        }
        p[i] = k;
      }
      return p;
    }

    public static List<Integer> getIndexes(String text, String pat) {
      List<Integer> arr = new ArrayList<>();
      int[] p = prefixFunction(pat);
      int k = 0;
      for (int i = 0; i < text.length(); i++) {
        while (k > 0 && text.charAt(i) != pat.charAt(k)) {
          k = p[k - 1];
        }
        if (text.charAt(i) == pat.charAt(k)) {
          ++k;
        }
        if (k == pat.length()) {
          arr.add((i + 1 - pat.length()));
          k = p[k - 1];
        }
      }
      return arr;
    }

    public static int[] prefixFunction(String s) {
      return prefixFunction(s.toCharArray());
    }

  }
}

