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.util.*;
import java.io.*;
import java.math.*;

public class Main {

	static PrintWriter pw = new PrintWriter(System.out);

	public static void main(String[] args) throws IOException, InterruptedException {
		Scanner sc = new Scanner(System.in);
		BigInteger n = BigInteger.valueOf(sc.nextLong());
		long b = sc.nextLong();
		pair[] arr = factors(b);
		long c = chk(n, arr[0]);
		for (int i = 1; i < arr.length; i++) {
			c = Math.min(c, chk(n, arr[i]));
		}
		pw.println(c);
		pw.close();
	}

	static long chk(BigInteger n, pair p) {
		long c = 0;
		BigInteger y = BigInteger.valueOf(p.x);
		while (n.divide(y).compareTo(BigInteger.valueOf(0)) > 0) {
			c += n.divide(y).longValue();
			y = y.multiply(BigInteger.valueOf(p.x));
		}
		return c / p.y;
	}

	static pair[] factors(long n) {
		ArrayList<pair> arrl = new ArrayList<>();
		long c = 0;
		while (n % 2 == 0) {
			n /= 2;
			c++;
		}
		if (c != 0) {
			arrl.add(new pair(2, c));
		}
		for (int i = 3; i <= Math.sqrt(n); i += 2) {
			c = 0;
			while (n % i == 0) {
				n /= i;
				c++;
			}
			if (c != 0) {
				arrl.add(new pair(i, c));
			}
		}
		if (n != 1) {
			arrl.add(new pair(n, 1));
		}
		pair[] arr = new pair[arrl.size()];
		int p = 0;
		for (pair k : arrl) {
			arr[p++] = k;
		}
		return arr;
	}

	static int countDivisors(int N) {
		int ans = 1;
		for (int p : primes) {
			if (p * p * p > N)
				break;
			int count = 1;
			while (N % p == 0) {
				N = N / p;
				count = count + 1;
			}
			ans = ans * count;
		}

		if (primes.contains(N))
			ans = ans * 2;
		else if (sp.contains((long) N))
			ans = ans * 3;
		else if (N != 1)
			ans = ans * 4;
		return ans;
	}

	static int divisors(int n) {
		int c = 0;
		for (int i = 1; i <= Math.sqrt(n); i++) {
			if (n % i == 0) {
				if (n / i == i) {
					c++;
				} else {
					c += 2;
				}
			}
		}
		return c;
	}

	static long bs(int x, int[] arr) {
		int start = 0, end = arr.length - 1;
		long ans = -1;
		while (start <= end) {
			int mid = (start + end) / 2;
			if (arr[mid] == x) {
				ans = mid;
				end = mid - 1;
			} else if (arr[mid] > x) {
				end = mid - 1;
			} else {
				start = mid + 1;
			}
		}
		return ans;
	}

	static long pow(long a, long e) {
		long res = 1;
		while (e > 0) {
			if ((e & 1) == 1)
				res *= a;
			a *= a;
			e >>= 1;
		}
		return res;
	}

	static HashSet<Integer> getFactorization(int x) {
		HashSet<Integer> ret = new HashSet<>();
		while (x != 1) {
			ret.add(lp[x]);
			x = x / lp[x];
		}
		return ret;
	}

	static int[] lp;
	static TreeSet<Integer> primes;
	static TreeSet<Long> sp;

	static void sieveLinear(int N) {
		primes = new TreeSet<Integer>();
		lp = new int[N + 1]; // lp[i] = least prime divisor of i
		for (int i = 2; i <= N; ++i) {
			if (lp[i] == 0) {
				primes.add(i);
				lp[i] = i;
			}
			int curLP = lp[i];
			for (int p : primes)// all primes smaller than or equal my lowest prime divisor
				if (p > curLP || p * 1l * i > N)
					break;
				else
					lp[p * i] = p;
		}
	}

	static class pair implements Comparable<pair> {
		long x;
		long y;

		public pair(long x, long y) {
			this.x = x;
			this.y = y;
		}

		public String toString() {
			return x + " " + y;
		}

		public boolean equals(Object o) {
			if (o instanceof pair) {
				pair p = (pair) o;
				return p.x == x && p.y == y;
			}
			return false;
		}

		public int hashCode() {
			return new Double(x).hashCode() * 31 + new Double(y).hashCode();
		}

		public int compareTo(pair other) {
			if (this.x == other.x) {
				return Long.compare(this.y, other.y);
			}
			return Long.compare(this.x, other.x);
		}
	}

	static class tuble implements Comparable<tuble> {
		int x;
		int y;
		int z;

		public tuble(int x, int y, int z) {
			this.x = x;
			this.y = y;
			this.z = z;
		}

		public String toString() {
			return x + " " + y + " " + z;
		}

		public int compareTo(tuble other) {
			if (this.x == other.x) {
				if (this.y == other.y)
					return this.z - other.z;
				return this.y - other.y;
			} else {
				return this.x - other.x;
			}
		}
	}

	static class Scanner {
		StringTokenizer st;
		BufferedReader br;

		public Scanner(InputStream s) {
			br = new BufferedReader(new InputStreamReader(s));
		}

		public boolean hasNext() {
			// TODO Auto-generated method stub
			return false;
		}

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

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

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

		public String nextLine() throws IOException {
			return br.readLine();
		}

		public double nextDouble() throws IOException {
			String x = next();
			StringBuilder sb = new StringBuilder("0");
			double res = 0, f = 1;
			boolean dec = false, neg = false;
			int start = 0;
			if (x.charAt(0) == '-') {
				neg = true;
				start++;
			}
			for (int i = start; i < x.length(); i++)
				if (x.charAt(i) == '.') {
					res = Long.parseLong(sb.toString());
					sb = new StringBuilder("0");
					dec = true;
				} else {
					sb.append(x.charAt(i));
					if (dec)
						f *= 10;
				}
			res += Long.parseLong(sb.toString()) / f;
			return res * (neg ? -1 : 1);
		}

		public boolean ready() throws IOException {
			return br.ready();
		}

	}
}