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.*;
public class CodeforcesEdu48 {
public static Scanner scn = new Scanner (System.in);
	public static void main(String[] args) {
	//	Q1();
	//	Q2();
		Q2n();
	}
	
	private static void Q2n() {
		int n = scn.nextInt();
		int m = scn.nextInt();
		int qn = scn.nextInt();
		String s = scn.next();
		String t = scn.next();
		int[][] q = new int[qn][2];
		for(int i =0;i<qn;i++) {
			q[i][0] = scn.nextInt()-1;
			q[i][1] = scn.nextInt()-1;
		}
		if(n<m) {
			for(int i = 0;i<qn;i++) {
				System.out.println(0);
			}
			return;
		}
		for(int i = 0;i<qn;i++) {
			int l = q[i][0];
			int r = q[i][1];
			int ans = KMPSearch(t, s.substring(l, r+1));
			if(ans==-1) {
				System.out.println(0);
			}else {
				System.out.println(ans);
			}
		}
		
	}
	 static int KMPSearch(String pat, String txt)
	    {
		 	int count = 0;
	        int M = pat.length();
	        int N = txt.length();
	 
	 
	        int lps[] = new int[M];
	        int j = 0;
	 
	       computeLPSArray(pat,M,lps);
	 
	        int i = 0; 
	        while (i < N)
	        {
	            if (pat.charAt(j) == txt.charAt(i))
	            {
	                j++;
	                i++;
	            }
	            if (j == M)
	            {
	           
	               int ans = (i-j);
	            	j = lps[j-1];
	            	count++;
	            }
	 
	           
	            else if (i < N && pat.charAt(j) != txt.charAt(i))
	            {
	           
	                if (j != 0)
	                    j = lps[j-1];
	                else
	                    i = i+1;
	            }
	        }
	        if(count!=0)return count;
	        return -1;
	    }
	 
	    static void computeLPSArray(String pat, int M, int lps[])
	    {
	     
	        int len = 0;
	        int i = 1;
	        lps[0] = 0; 
	 

	        while (i < M)
	        {
	            if (pat.charAt(i) == pat.charAt(len))
	            {
	                len++;
	                lps[i] = len;
	                i++;
	            }
	            else 
	            {
	                
	                if (len != 0)
	                {
	                    len = lps[len-1];
	 
	                
	                }
	                else 
	                {
	                    lps[i] = len;
	                    i++;
	                }
	            }
	        }
	    }
	private static void Q2() {
		int n = scn.nextInt();
		int m = scn.nextInt();
		int qn = scn.nextInt();
		String s = scn.next();
		String t = scn.next();
		int[][] q = new int[qn][2];
		for(int i =0;i<qn;i++) {
			q[i][0] = scn.nextInt()-1;
			q[i][1] = scn.nextInt()-1;
		}
		if(n<m) {
			for(int i = 0;i<qn;i++) {
				System.out.println(0);
			}
			return;
		}
		int[] a = new int[n];
		int st =0;
		int i = 0;
		int last = 0;
		int count = 0;
		while(i<n) {
			int pos = s.indexOf(t,i);
			if(pos==-1) {
				for(int j =last+1;j<n;j++) {
					a[j] = count;
				}
				break;
			}else {
				count++;
				int nlast = pos+t.length()-1;
				a[pos+t.length()-1] = count;
				for(int j =last+1;j<nlast;j++) {
					a[j] = count-1;
				}
				last = nlast;
				i = pos+1;
			}
		}
		for(int j = 0;j<qn;j++) {
			int l = q[j][0];
			int r = q[j][1];
			if(r-l>=t.length())
			System.out.println(a[r]-a[l]);
			else {
				int ans = a[r]-a[l];
				if(ans>0)System.out.println(ans-1);
				else System.out.println(0);
			}
				
		}
	}
	private static void Q1() {
		int n  = scn.nextInt();
		int m = scn.nextInt();
		int[]arr = new int[n];
		for(int i = 0;i<n;i++) {
			arr[i] = scn.nextInt();
		}
		int left = m;
		int[] sol = new int[n];
		long pg = 1;
		for(int i = 0;i<n;i++) {
			if(arr[i]<left) {
				left-=arr[i];
				sol[i] = 0;
			}else {
				int np = (arr[i]-left)/m;
				sol[i] = np+1;
			//	pg+=np;
				left = m- (arr[i]-left)%m ;
			}
			System.out.print(sol[i]+" ");
		}
		System.out.println();
	}

}
