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).
#!/usr/bin/env python
"""
This file is part of https://github.com/cheran-senthil/PyRival
Copyright 2019 Cheran Senthilkumar <hello@cheran.io>

"""
from __future__ import division, print_function

import cmath
import itertools
import math
import operator as op
import random
import sys
from atexit import register
from bisect import bisect_left, bisect_right
from collections import Counter
# from copy import deepcopy
# from decimal import Decimal
# from difflib import SequenceMatcher
from functools import reduce
# from heapq import heappop, heappush
from io import BytesIO, FileIO, StringIO

if sys.version_info[0] < 3:

    class dict(dict):
        """dict() -> new empty dictionary"""

        def items(self):
            """D.items() -> a set-like object providing a view on D's items"""
            return dict.iteritems(self)

        def keys(self):
            """D.keys() -> a set-like object providing a view on D's keys"""
            return dict.iterkeys(self)

        def values(self):
            """D.values() -> an object providing a view on D's values"""
            return dict.itervalues(self)

    input = raw_input
    range = xrange

    filter = itertools.ifilter
    map = itertools.imap
    zip = itertools.izip

INP_FILE = 0
OUT_FILE = 1

if sys.version_info[0] < 3:
    sys.stdin = BytesIO(FileIO(INP_FILE).read())
    sys.stdout = BytesIO()
    register(lambda: FileIO(OUT_FILE, 'w').write(sys.stdout.getvalue()))
else:
    sys.stdin = StringIO(FileIO(INP_FILE).read().decode())
    sys.stdout = StringIO()
    register(lambda: FileIO(OUT_FILE, 'w').write(sys.stdout.getvalue().encode(
    )))

input = lambda: sys.stdin.readline().rstrip('\r\n')

def gcd(a, b):
    while b:
        a, b = b, a%b
    return a


def memodict(f):
    """ Memoization decorator for a function taking a single argument. """

    class memodict(dict):
        def __missing__(self, key):
            ret = self[key] = f(key)
            return ret

    return memodict().__getitem__


def is_prime(n):
    """
    Deterministic variant of the Miller-Rabin primality test to determine
    whether a given number (upto 2**64) is prime.

    Parameters
    ----------
    n : int
        n >= 0, an integer to be tested for primality.

    Returns
    -------
    bool
        False if n is composite, otherwise True.
    """
    if n in [2, 3, 5, 13, 19, 73, 193, 407521, 299210837]:
        return True

    if (n in [0, 1]) or (any(
            n % p == 0
            for p in [2, 3, 5, 13, 19, 73, 193, 407521, 299210837])):
        return False

    d, s = n - 1, 0
    while not d & 1:
        d, s = d >> 1, s + 1

    def try_composite(a):
        if pow(a, d, n) == 1:
            return False
        for i in range(s):
            if pow(a, 2**i * d, n) == n - 1:
                return False
        return True

    return not any(
        try_composite(w)
        for w in [2, 325, 9375, 28178, 450775, 9780504, 1795265022])


@memodict
def pollard_rho(n):
    if n == 1:
        return Counter()

    if is_prime(n):
        return Counter({n: 1})

    y, c, m = random.randint(1, n - 1), random.randint(1,
                                                       n - 1), random.randint(
                                                           1, n - 1)
    g, r, q = 1, 1, 1

    while g == 1:
        x, k = y, 0

        for _ in range(r):
            y = (y * y + c) % n

        while (k < r) and (g == 1):
            ys = y

            for _ in range(min(m, r - k)):
                y = (y * y + c) % n
                q = (q * abs(x - y)) % n

            g = gcd(q, n)
            k += m

        r *= 2

    if g == n:
        while True:
            ys = (ys * ys + c) % n
            g = gcd(abs(x - ys), n)
            if g > 1:
                break

    return pollard_rho(g) + pollard_rho(n // g)


def factors(n):
    """
    Prime factorization using Pollard's rho algorithm.

    Parameters
    ----------
    n : int
        n > 0, an integer to be factorized.

    Returns
    -------
    prime_factors : Counter
        Counter of the prime factors of n.
    """
    prime_factors = Counter()

    def ilog(n, p):
        cnt = 0
        while n % p == 0:
            n, cnt = n // p, cnt + 1
        return n, cnt

    if not n & 1:
        n, prime_factors[2] = ilog(n, 2)
    if n % 3 == 0:
        n, prime_factors[3] = ilog(n, 3)

    i = 5
    while i * i <= min(n, 4294967295):
        if n % i == 0:
            n, prime_factors[i] = ilog(n, i)
        i += 2 if i % 3 == 2 else 4

    if n == 1:
        return prime_factors

    if n <= 4294967295:
        prime_factors[n] = 1
        return prime_factors

    return prime_factors + pollard_rho(n)


def main():
    n, b = map(int, input().split())

    f = factors(b)
    m = float('inf')

    for prime, count in f.items():
        a = n

        r = 0
        while a:
            r += a // prime
            a //= prime

        m = min(m, r // count)

    print(m)


if __name__ == '__main__':
    main()
