The number "zero" is called "love" (or "l'oeuf" to be precise, literally means "egg" in French), for example when denoting the zero score in a game of tennis. 

Aki is fond of numbers, especially those with trailing zeros. For example, the number 9200 has two trailing zeros. Aki thinks the more trailing zero digits a number has, the prettier it is.

However, Aki believes, that the number of trailing zeros of a number is not static, but depends on the base (radix) it is represented in. Thus, he considers a few scenarios with some numbers and bases. And now, since the numbers he used become quite bizarre, he asks you to help him to calculate the beauty of these numbers.

Given two integers n and b (in decimal notation), your task is to calculate the number of trailing zero digits in the b-ary (in the base/radix of b) representation of n ! ([factorial](https://en.wikipedia.org/wiki/Factorial) of n). 

Input

The only line of the input contains two integers n and b (1 ≤ n ≤ 10^{18}, 2 ≤ b ≤ 10^{12}).

Output

Print an only integer — the number of trailing zero digits in the b-ary representation of n!

Examples

Input

6 9


Output

1


Input

38 11


Output

3


Input

5 2


Output

3


Input

5 10


Output

1

Note

In the first example, 6!_{(10)} = 720_{(10)} = 880_{(9)}.

In the third and fourth example, 5!_{(10)} = 120_{(10)} = 1111000_{(2)}.

The representation of the number x in the b-ary base is d_1, d_2, …, d_k if x = d_1 b^{k - 1} + d_2 b^{k - 2} + … + d_k b^0, where d_i are integers and 0 ≤ d_i ≤ b - 1. For example, the number 720 from the first example is represented as 880_{(9)} since 720 = 8 ⋅ 9^2 + 8 ⋅ 9 + 0 ⋅ 1.

You can read more about bases [here](https://en.wikipedia.org/wiki/Radix).
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.BufferedWriter;
import java.io.IOException;
import java.util.HashMap;
import java.io.InputStreamReader;
import java.io.UncheckedIOException;
import java.nio.charset.Charset;
import java.util.StringTokenizer;
import java.util.Map;
import java.util.Map.Entry;
import java.io.Writer;
import java.io.OutputStreamWriter;
import java.io.BufferedReader;
import java.util.regex.Pattern;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author mikit
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        LightScanner in = new LightScanner(inputStream);
        LightWriter out = new LightWriter(outputStream);
        CTrailingLovesOrLoeufs solver = new CTrailingLovesOrLoeufs();
        solver.solve(1, in, out);
        out.close();
    }

    static class CTrailingLovesOrLoeufs {
        public void solve(int testNumber, LightScanner in, LightWriter out) {
            Debug.enable("src");
            long n = in.longs(), b = in.longs();
            long ans = Long.MAX_VALUE;
            Map<Long, Integer> pf = IntMath.primeFactorize(b);
            for (Map.Entry<Long, Integer> ent : pf.entrySet()) {
                long fc = count(ent.getKey(), n);
                //System.out.println(ent.getKey()+"->"+fc);
                ans = Math.min(ans, fc / ent.getValue());
            }
            out.ans(ans).ln();
        }

        private static long count(long p, long n) {
            if (p > n) {
                return 0;
            }
            long q = p;
            long ans = 0;
            while (true) {
                ans += n / q;
                if (n / q < p || (q = q * p) > n || q < 0) {
                    return ans;
                }
            }
        }

    }

    static class LightScanner {
        private BufferedReader reader = null;
        private StringTokenizer tokenizer = null;

        public LightScanner(InputStream in) {
            reader = new BufferedReader(new InputStreamReader(in));
        }

        public String string() {
            if (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new UncheckedIOException(e);
                }
            }
            return tokenizer.nextToken();
        }

        public long longs() {
            return Long.parseLong(string());
        }

    }

    static class LightWriter implements AutoCloseable {
        private final Writer out;
        private boolean autoflush = false;
        private boolean breaked = true;

        public LightWriter(Writer out) {
            this.out = out;
        }

        public LightWriter(OutputStream out) {
            this(new BufferedWriter(new OutputStreamWriter(out, Charset.defaultCharset())));
        }

        public LightWriter print(char c) {
            try {
                out.write(c);
                breaked = false;
            } catch (IOException ex) {
                throw new UncheckedIOException(ex);
            }
            return this;
        }

        public LightWriter print(String s) {
            try {
                out.write(s, 0, s.length());
                breaked = false;
            } catch (IOException ex) {
                throw new UncheckedIOException(ex);
            }
            return this;
        }

        public LightWriter ans(String s) {
            if (!breaked) {
                print(' ');
            }
            return print(s);
        }

        public LightWriter ans(long l) {
            return ans(Long.toString(l));
        }

        public LightWriter ln() {
            print(System.lineSeparator());
            breaked = true;
            if (autoflush) {
                try {
                    out.flush();
                } catch (IOException ex) {
                    throw new UncheckedIOException(ex);
                }
            }
            return this;
        }

        public void close() {
            try {
                out.close();
            } catch (IOException ex) {
                throw new UncheckedIOException(ex);
            }
        }

    }

    static final class IntMath {
        private IntMath() {
        }

        public static Long getPrimeFactor(long a) {
            if (a <= 1) {
                return null;
            } else if ((a & 1) == 0) {
                return 2L;
            }
            for (long i = 3; i * i <= a; i += 2) {
                if (a % i == 0) {
                    return i;
                }
            }
            return a;
        }

        public static Map<Long, Integer> primeFactorize(long p) {
            Long f = null;
            Map<Long, Integer> factor = new HashMap<>();
            while ((f = IntMath.getPrimeFactor(p)) != null) {
                factor.merge(f, 1, (x, y) -> x + y);
                p /= f;
            }
            if (p > 1) {
                factor.merge(p, 1, (x, y) -> x + y);
            }
            return factor;
        }

    }

    static class Debug {
        private static final String DEBUG_CALL_PATTERN = "^.+\\.debug\\((.+)\\);.*$";
        private static Pattern debugRegex;
        private static boolean enabled = false;
        private static String src;

        public static void enable(String s) {
            enabled = true;
            src = s;
            if (debugRegex == null) {
                debugRegex = Pattern.compile(DEBUG_CALL_PATTERN);
            }
        }

    }
}

