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

public class DRedo {
	public static void main(String[] args) throws Exception{
		InputReader in = new InputReader(System.in);
		PrintWriter out = new PrintWriter(System.out);
		
		int b = in.nextInt();
		int d = in.nextInt();
		
		String a = in.nextToken();
		String c = in.nextToken();
		
		//keep replicating c until before numReplicate > b
		long lengthA = 0;
		long maxLength = b * a.length();
		int numCReplicate = 0;
		//how many C replications does it take first get to a[i]
		Integer[] cReps = new Integer[a.length()];
		//how many aSteps
		Long[] aConsume = new Long[a.length()];
		boolean cycled = false;
		
		while(lengthA <= maxLength){
			int aIndex = (int) (lengthA % a.length());
			if(!cycled && cReps[aIndex] != null){
				cycled = true;
				long cRep = numCReplicate - cReps[aIndex];
				long cycleLength = lengthA - aConsume[aIndex];
				long cycleTimes = (maxLength-lengthA) / cycleLength;
				lengthA += (long)cycleTimes * cycleLength;
				numCReplicate += (long) cycleTimes * cRep;
			}else{
				cReps[aIndex] = numCReplicate;
				aConsume[aIndex] = lengthA;
				int stepToReplicateC = 0;
				for(int cIndex = 0; cIndex < c.length(); cIndex++){
					while(c.charAt(cIndex) != a.charAt(aIndex)){
						lengthA++;
						aIndex++;
						stepToReplicateC++;
						
						if(stepToReplicateC > 10000){
							out.println(0);
							out.close();
							return;
						}
						if(aIndex == a.length())
							aIndex = 0;
					}
					lengthA++;
					aIndex++;
					if(aIndex == a.length())
						aIndex = 0;
				}
				
				numCReplicate++;
			}
		}
		
		numCReplicate--;
		//answer = numReplicate / d
		out.println(numCReplicate/d);
		
		out.close();
	}
	
	static class InputReader {
		private InputStream stream;
		private byte[] buf = new byte[1024];
		private int curChar;
		private int numChars;
		private SpaceCharFilter filter;

		public InputReader(InputStream stream) {
			this.stream = stream;
		}
		
		
		public 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++];
		}

		public int nextInt() {
			int c = read();
			while (isSpaceChar(c))
				c = read();
			int sgn = 1;
			if (c == '-') {
				sgn = -1;
				c = read();
			}
			int res = 0;
			do {
				if (c < '0' || c > '9')
					throw new InputMismatchException();
				res *= 10;
				res += c - '0';
				c = read();
			} while (!isSpaceChar(c));
			return res * sgn;
		}

		public long nextLong() {
			int c = read();
			while (isSpaceChar(c))
				c = read();
			int sgn = 1;
			if (c == '-') {
				sgn = -1;
				c = read();
			}
			long res = 0;
			do {
				if (c < '0' || c > '9')
					throw new InputMismatchException();
				res *= 10;
				res += c - '0';
				c = read();
			} while (!isSpaceChar(c));
			return res * sgn;
		}
		

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

		public boolean isSpaceChar(int c) {
			if (filter != null)
				return filter.isSpaceChar(c);
			return isWhitespace(c);
		}

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

		public interface SpaceCharFilter {
			public boolean isSpaceChar(int ch);
		}
	}
}
