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 Contest187 {

    public static void main(String[] args) throws IOException {
        new Contest187().run();
    }

    void solve() throws IOException {
        long b = nextLong();
        long d = nextLong();
        String a = nextToken();
        String c = nextToken();
        for(int i = 0; i < c.length(); ++i) {
            boolean found = false;
            for(int j = 0; j < a.length() && !found; ++j)
                found = c.charAt(i) == a.charAt(j);
            if(!found) {
                out.println(0);
                return;
            }
        }

        long last_aloop[] = new long[a.length()];
        long last_cloop[] = new long[a.length()];
        for(int i = 0; i < last_aloop.length; ++i)
            last_aloop[i] = -1;
        for(int i = 0; i < last_cloop.length; ++i)
            last_cloop[i] = -1;
        int a_pos = 0;
        long a_loop = 0;
        int c_pos = 0;
        long c_loop = 0;
        boolean can_jump = true;
        while(true) {
            for(; a.charAt(a_pos) != c.charAt(c_pos) && a_loop < b; ) {
                ++a_pos;
                if(a_pos >= a.length()) {
                    a_pos = 0;
                    ++a_loop;
                }
            }

            if(a.charAt(a_pos) != c.charAt(c_pos) || a_loop >= b) break;

            if(c_pos == 0 && last_aloop[a_pos] != -1 && last_cloop[a_pos] != -1 && last_cloop[a_pos] != c_loop && can_jump) {
                long dist = a_loop - last_aloop[a_pos];
                long delta = c_loop - last_cloop[a_pos];
                long jump = (b - a_loop - 1) / dist;
                c_loop += jump * delta;
                a_loop += jump * dist;
                can_jump = false;
            }
            else {
                if(c_pos == 0) {
                    last_aloop[a_pos] = a_loop;
                    last_cloop[a_pos] = c_loop;
                }
                ++c_pos;
                if(c_pos >= c.length()) {
                    c_pos = 0;
                    ++c_loop;
                }
                ++a_pos;
                if(a_pos >= a.length()) {
                    a_pos = 0;
                    ++a_loop;
                }
            }
        }
        long p = c_loop / d;
        out.println(p);
    }

    BufferedReader br;
    StringTokenizer st;
    PrintWriter out;

    public String nextToken() throws IOException {
        while(st == null || !st.hasMoreTokens()) {
            st = new StringTokenizer(br.readLine());
        }

        return st.nextToken();
    }

    public int nextInt() throws IOException {
        return Integer.parseInt(nextToken());
    }

    public long nextLong() throws  IOException {
        return Long.parseLong(nextToken());
    }

    public double nextDouble() throws IOException {
        return Double.parseDouble(nextToken());
    }

    void run() throws IOException {
        boolean oj = System.getProperty("ONLINE_JUDGE") != null;

        br = new BufferedReader( new InputStreamReader( oj ? System.in : new FileInputStream("input.txt")));
        out = new PrintWriter( oj ? System.out : new FileOutputStream("output.txt"));

        solve();

        out.close();
    }

}
