Let's introduce the designation <image>, where x is a string, n is a positive integer and operation " + " is the string concatenation operation. For example, [abc, 2] = abcabc.

We'll say that string s can be obtained from string t, if we can remove some characters from string t and obtain string s. For example, strings ab and aсba can be obtained from string xacbac, and strings bx and aaa cannot be obtained from it.

Sereja has two strings, w = [a, b] and q = [c, d]. He wants to find such maximum integer p (p > 0), that [q, p] can be obtained from string w.

Input

The first line contains two integers b, d (1 ≤ b, d ≤ 107). The second line contains string a. The third line contains string c. The given strings are not empty and consist of lowercase English letters. Their lengths do not exceed 100.

Output

In a single line print an integer — the largest number p. If the required value of p doesn't exist, print 0.

Examples

Input

10 3
abab
bab


Output

3
import java.io.*;
import java.util.*;

public class B implements Runnable{
	public static void main (String[] args) {new Thread(null, new B(), "_cf", 1 << 28).start();}

	int b, d, n, m;
	String a, c;
	
	public void run() {
		FastScanner fs = new FastScanner();
		PrintWriter out = new PrintWriter(System.out);
		System.err.println("Go!");
		
		b = fs.nextInt(); d = fs.nextInt();
		a = fs.next(); n = a.length();
		c = fs.next(); m = c.length();

		int[] matches = new int[m];
		/*
		 * matches[i] = x means that if I were to start at position i
		   in string c and start matching from the beginning of a, I would
		   match x characters (x > m means that we're matching multiple
		   occurences of c in one instance of a)
		*/

		for(int i = 0; i < m; i++) {
			//build matches[i] starting at i in string c.
			for(int j = 0; j < n; j++) {
				//look at every character in a and see if it matches
				//the current character of c that we're looking for.
				int look = (i + matches[i]) % m; //if we've matched matches[i] we need whatever
				 								 //comes next (it might wrap around to the next
												 //occurence of c)
				if(a.charAt(j) == c.charAt(look)) {
					//it matched!
					matches[i]++;
				}
			}
		}
		
		int res = 0;
		//res = number of matched characters of c so far (including multiple
		//instances of c). We start at 0 characters matched
		
		//for every block of a that we have
		for(int i = 0; i < b; i++) {
			//if we've matched res characters, res % m tells us what
			//we're looking for next in the string. Since this is one
			//block of a, we just add the total number of characters that
			//it matches and keep going.
			res += matches[res % m];
		}
		
		//an occurrence of q is m * d characters of c matched
		//so if we've matched res, the largest p is res / (m * d)
		res /= m * d;
		
		out.println(res);
		out.close();
	}

	class FastScanner {
		public int BS = 1<<16;
		public char NC = (char)0;
		byte[] buf = new byte[BS];
		int bId = 0, size = 0;
		char c = NC;
		double num = 1;
		BufferedInputStream in;

		public FastScanner() {
			in = new BufferedInputStream(System.in, BS);
		}

		public FastScanner(String s) throws FileNotFoundException {
			in = new BufferedInputStream(new FileInputStream(new File(s)), BS);
		}

		public char nextChar(){
			while(bId==size) {
				try {
					size = in.read(buf);
				}catch(Exception e) {
					return NC;
				}                
				if(size==-1)return NC;
				bId=0;
			}
			return (char)buf[bId++];
		}

		public int nextInt() {
			return (int)nextLong();
		}

		public long nextLong() {
			num=1;
			boolean neg = false;
			if(c==NC)c=nextChar();
			for(;(c<'0' || c>'9'); c = nextChar()) {
				if(c=='-')neg=true;
			}
			long res = 0;
			for(; c>='0' && c <='9'; c=nextChar()) {
				res = (res<<3)+(res<<1)+c-'0';
				num*=10;
			}
			return neg?-res:res;
		}

		public double nextDouble() {
			double cur = nextLong();
			return c!='.' ? cur:cur+nextLong()/num;
		}

		public String next() {
			StringBuilder res = new StringBuilder();
			while(c<=32)c=nextChar();
			while(c>32) {
				res.append(c);
				c=nextChar();
			}
			return res.toString();
		}

		public String nextLine() {
			StringBuilder res = new StringBuilder();
			while(c<=32)c=nextChar();
			while(c!='\n') {
				res.append(c);
				c=nextChar();
			}
			return res.toString();
		}

		public boolean hasNext() {
			if(c>32)return true;
			while(true) {
				c=nextChar();
				if(c==NC)return false;
				else if(c>32)return true;
			}
		}
		
		public int[] nextIntArray(int n) {
			int[] res = new int[n];
			for(int i = 0; i < n; i++) res[i] = nextInt();
			return res;
		}
		
	}

}