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

public class Problem1016B {

	public static void main(String[] args) throws Exception {
		InputStream inputStream = System.in;
		OutputStream outputStream = System.out;
		InputReader in = new InputReader(inputStream);
		PrintWriter out = new PrintWriter(outputStream);

		int n = in.nextInt();
		int m = in.nextInt();
		int q = in.nextInt();

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

		int[][] qs = in.nextIntMatrix(q, 2);

		int lastIndex = 0;
		ArrayList<Integer> occs = new ArrayList<>();
		while (lastIndex != -1) {

			lastIndex = s.indexOf(t, lastIndex);

			if (lastIndex != -1) {
				occs.add(lastIndex + 1);
				lastIndex++;
			}
		}

		for (int i = 0; i < q; i++) {
			final int que = i;
			out.println(occs.stream().filter(oc -> qs[que][0] <= oc && qs[que][1] >= oc + m - 1).count());
		}

		out.close();
		return;
	}

	static class InputReader {
		BufferedReader reader;

		StringTokenizer tokenizer;

		public InputReader(InputStream stream) {
			reader = new BufferedReader(new InputStreamReader(stream), 32768);
			tokenizer = null;
		}

		private String next() {
			while (tokenizer == null || !tokenizer.hasMoreTokens()) {
				try {
					tokenizer = new StringTokenizer(reader.readLine(), " \t\n\r\f,");
				} catch (IOException e) {
					throw new RuntimeException(e);
				}
			}
			return tokenizer.nextToken();
		}

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

		public long nextLong() {
			return Long.parseLong(next());
		}

		public int[] nextIntArray(int n) {
			return nextIntArray(n, 0);
		}

		public int[] nextIntArray(int n, int offset) {
			int[] a = new int[n];
			for (int i = 0; i < n; i++) {
				a[i] = nextInt() + offset;
			}
			return a;
		}

		public int[][] nextIntMatrix(int n, int m) {
			int[][] a = new int[n][m];
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < m; j++) {
					a[i][j] = nextInt();
				}
			}
			return a;
		}

		public String nextLine() {
			return next();
		}

		public char[] nextLineCharArray() {
			return next().toCharArray();
		}
	}

}