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

public class cf1016b {

	public static void main(String[] args) {
		FastScanner in = new FastScanner(System.in);
		int N = in.nextInt();
		int M = in.nextInt();
		int Q = in.nextInt();
		char[] s = in.next().toCharArray();
		char[] t = in.next().toCharArray();

		int[] start = new int[N + 1];
		for(int i = 0; i < N; i++)
			if(equals(s, t, i))
				start[i + 1]++;
		
		for(int i = 1; i < start.length; i++)
			start[i] += start[i - 1];
		
		StringBuilder ans = new StringBuilder();
		
		for(int i = 0; i < Q; i++) {
			int l = in.nextInt() - 1;
			int r = in.nextInt() - t.length + 1;
			if(r < l || r < 0)
				ans.append(0);
			else
				ans.append(start[r] - start[l]);
			
			ans.append('\n');
		}
		
		System.out.print(ans);
	}
	
	static boolean equals(char[] a, char[] b, int aInd) {
		if(a.length < b.length || aInd + b.length > a.length)
			return false;
		
		for(int i = aInd; i < aInd + b.length; i++)
			if(a[i] != b[i - aInd])
				return false;
		
		return true;
	}
	
	//Credits to Matt Fontaine
	static class FastScanner{
	   private InputStream stream;                                                                                         
	   private byte[] buf = new byte[1024];                                                                                
	   private int curChar;                                                                                                
	   private int numChars;                                                                                               

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

	   int read()
	   {
	      if (numChars == -1)
	         throw new InputMismatchException();                                                                           
	      if (curChar >= numChars){
	         curChar = 0;                                                                                                  
	         try{
	            numChars = stream.read(buf);                                                                               
	         } catch (IOException e) {
	            throw new InputMismatchException();                                                                        
	         }
	         if (numChars <= 0)
	            return -1;                                                                                                 
	      }
	      return buf[curChar++];                                                                                           
	   }

	   boolean isSpaceChar(int c)
	   {
	      return c==' '||c=='\n'||c=='\r'||c=='\t'||c==-1;                                                                 
	   }

	   boolean isEndline(int c)
	   {
	      return c=='\n'||c=='\r'||c==-1;                                                                                  
	   }

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

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

	   double nextDouble()
	   {
	      return Double.parseDouble(next());                                                                               
	   }

	   String next(){
	      int c = read();                                                                                                  
	      while (isSpaceChar(c))
	         c = read();                                                                                                   
	      StringBuilder res = new StringBuilder();                                                                         
	      do{
	         res.appendCodePoint(c);                                                                                       
	         c = read();                                                                                                   
	      }while(!isSpaceChar(c));                                                                                         
	      return res.toString();                                                                                           
	   }

	   String nextLine(){
	      int c = read();                                                                                                  
	      while (isEndline(c))
	         c = read();                                                                                                   
	      StringBuilder res = new StringBuilder();                                                                         
	      do{
	         res.appendCodePoint(c);                                                                                       
	         c = read();                                                                                                   
	      }while(!isEndline(c));                                                                                           
	      return res.toString();                                                                                           
	   }
	}
}
