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.util.*;
import java.io.BufferedWriter;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.Writer;

public class B1016 {
    static class OutputWriter {
        private final PrintWriter writer;
    
        public OutputWriter(OutputStream outputStream) {
            writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
        }
    
        public OutputWriter(Writer writer) {
            this.writer = new PrintWriter(writer);
        }
    
        public void print(int[] array) {
            for (int i = 0; i < array.length; i++) {
                if (i != 0)
                    writer.print(' ');
                writer.print(array[i]);
            }
        }
    
        public void printLine(int[] array) {
            print(array);
            writer.println();
        }
    
        public void close() {
            writer.close();
        }
    
    }

    static class Pair {
        int value;
        int index;
        Pair(int value, int index) {
            this.value = value;
            this.index = index;
        }
    }
    static class MyComparator implements Comparator<Pair> {
        @Override
        public int compare(Pair p1, Pair p2) {
            if (p1.value != p2.value) return p1.value - p2.value;
            return p1.index - p2.index;
        }
    }
    public static void main(String[] args) {
		OutputStream outputStream = System.out;
        OutputWriter out = new OutputWriter(outputStream);
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        Scanner sc=  new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int q =sc.nextInt();
        sc.nextLine();
        String a = sc.nextLine();
        String b = sc.nextLine();
        int index = a.indexOf(b);
        int[] indexes = new int[n];
        while(index >= 0) {
            //System.out.println(index+m-1);
            indexes[index+m-1] = 1;
            index = a.indexOf(b, index+1);
        }
        //out.printLine(indexes);
        for (int i=1; i<indexes.length; i++) {
            indexes[i] += indexes[i-1];
        }
        //out.printLine(indexes);
        
        for (int i=0; i<q; i++) {
            int x = sc.nextInt();
            int y = sc.nextInt();
            if (y-x+1 < b.length()) System.out.println(0);
            else if (x == 1) System.out.println(indexes[y-1]);
            else if (x == y) {
                if (b.length()==1 &&  a.charAt(x-1) == b.charAt(0)) System.out.println(1);
                else System.out.println(0);
            }
            else  System.out.println(indexes[y-1]-indexes[x-2+m-1]);
        }
        
		//int n = in.readInt();
        //int[] temparr = IOUtils.readIntArray(in, n);
        //int[] rating = new int[n];
        //out.printLine(indexes);
        out.close();
    }
}