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.ArrayList;
import java.util.List;
import java.util.Scanner;

public class SegmentOccurences {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    String[] str = sc.nextLine().split(" ");
    int n = Integer.parseInt(str[0]);
    int m = Integer.parseInt(str[1]);
    int q = Integer.parseInt(str[2]);

    String s = sc.nextLine();
    String t = sc.nextLine();

    int[][] qu = new int[q][2];
    for (int i = 0; i < q; i++) {
      str = sc.nextLine().split(" ");
      qu[i][0] = Integer.parseInt(str[0]);
      qu[i][1] = Integer.parseInt(str[1]);
    }

    List<int[]> xx = new ArrayList<>();
    int k = 0;
    for (int i = 0; i + m <= s.length(); i++) {
      String temp = s.substring(i, i + m);
      if (temp.equalsIgnoreCase(t)) {
        int[] range = new int[2];
        range[0] = i + 1;
        range[1] = i + t.length();
        xx.add(range);
      }
    }

    for (int i = 0; i < q; i++) {
      int count = 0;
      if (xx.size() == s.length()) {
        count = qu[i][1] - qu[i][0] + 1;
      } else {
        for (int j = 0; j < xx.size(); j++) {
          if (xx.get(j)[0] >= qu[i][0] && xx.get(j)[1] <= qu[i][1]) {
            count++;
          }
          if (xx.get(j)[1] > qu[i][1]) {
            break;
          }
        }
      }
      System.out.println(count);
    }
  }
}
