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 of $n$). 


-----Input-----

The only line of the input contains two integers $n$ and $b$ ($1 \le n \le 10^{18}$, $2 \le b \le 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, \ldots, d_k$ if $x = d_1 b^{k - 1} + d_2 b^{k - 2} + \ldots + d_k b^0$, where $d_i$ are integers and $0 \le d_i \le b - 1$. For example, the number $720$ from the first example is represented as $880_{(9)}$ since $720 = 8 \cdot 9^2 + 8 \cdot 9 + 0 \cdot 1$.

You can read more about bases here.

Difficulty: interview

Starter code:

Solutions:
n, k = map(int, input().split())
a = []
i = 2
while (i * i <= k):
    if (k % i == 0):
        a.append([i, 0])
        while (k % i == 0):
            a[len(a) - 1][1] += 1
            k //= i
    i += 1
if (k > 1):
    a.append([k, 1])
ans = 10 ** 20
for i in a:
    cnt = 0
    x = i[0]
    while (x <= n):
        cnt += n // x;
        x *= i[0]
    ans = min(ans, cnt // i[1])
print(ans)

b,a=list(map(int,input().split()))
delit=[]
st=[]
i=2
uk=-1
while i*i<=a:
    if a%i==0:
        delit.append(i)
        uk+=1
        st.append(0)
        while a%i==0:
            a//=i
            st[uk]+=1
    i+=1
if a>1:
    delit.append(a)
    st.append(1)
coun=0
colvo=[0]*len(st)
cop=b
for i in range(len(delit)):
    while cop>=delit[i]:
        colvo[i]+=cop//delit[i]
        cop//=delit[i]
    cop=b
coun=colvo[i]//st[i]
for i in range (len(st)):
    if colvo[i]//st[i]<coun:
        coun=colvo[i]//st[i]
print(coun)


def factorial_1(n: int):
    for i in range(2, n+1):
        if i > n**0.5:
            return n
        elif n % i == 0:
            return i


def factorial_2(n: int):
    res = dict()
    while n > 1:
        f_now = factorial_1(n)
        n //= f_now
        res[f_now] = res.get(f_now, 0) + 1
    return res


n, k = map(int, input().split())
f_k, x = factorial_2(k), float('inf')
for key, val in f_k.items():
    qua_f, pow_ = 0, key
    while pow_ <= n:
        qua_f += n//pow_
        pow_ *= key
    x = min(x, qua_f//val)
print(x)

from math import sqrt
def fact(a):
    nonlocal g
    nonlocal h
    for i in range(2, int(sqrt(a)) + 1):
        k = 0
        if a % i == 0:
            g.append(i)
        while a % i == 0:
            a = a // i
            k += 1
        if k != 0:
            h.append(k)
    if a > 1:
        g.append(a)
        h.append(1)
n, k = list(map(int, input().split()))
g = []
h = []
f = fact(k)
mini = 100000000000000000000000000000000000000000000000000000000000
for i in range(len(g)):
    k1 = 0
    v = g[i]
    while n // g[i] > 0:
        k1 += n // g[i]
        g[i] *= v
    if k1 // h[i] < mini:
        mini = k1 // h[i]
print(mini)


'''input
5 2
5 10
6 9
38 11
'''
n, b = map(int, input().split())

pm = 1
k = 0
i = 2
ans = float("inf")

def calc(n, b, k):
	res = 0
	t = pm
	while t <= n:
		res += n // t
		t *= pm
	return res // k

while i * i <= b:
	if b % i == 0:
		pm = i
		k = 0
		while b % i == 0:
			b //= i
			k += 1
		ans = min(ans, calc(n, b, k))
	i += 1
if b > 1:
	pm = b
	k = 1
	ans = min(ans, calc(n, b, k))
print(ans)

def start(x, cnt):
    nonlocal ans
    i = x
    res = 0
    while i <= n:
        res += n // i
        i *= x
    ans = min(ans, res // cnt)

n, b = map(int, input().split())
nb = b
ans = 1e20
i = 2
while i * i <= b:
    if nb % i == 0:
        cnt = 0
        while nb % i == 0:
            cnt += 1
            nb //= i
        start(i, cnt)
    i += 1
if nb > 1:
    start(nb, 1)
print(ans)

n, b = map(int, input().split())
ans = 0
d = 2
bf = b
factors = []
while d * d <= b:
	if b % d == 0:
		cnt = 0
		while b % d == 0:
			cnt += 1
			b = b // d
		factors.append((d, cnt))
	d += 1

if b > 1:
	factors.append((b, 1))

def calc(x, y):
	yst = y
	ans = 0
	while yst <= x:
		ans += x // yst
		yst *= y
	return ans

ln = len(factors)
ans = min(calc(n, p[0]) // p[1] for p in factors)
print(ans)

from math import sqrt
n, b= [int(i) for i in input().split()]
def geg(n, k, l):
    if k<=n:
        return n//k+geg(n, k*l, l)
    else:
        return 0
def fact(b, n):
    D={}
    for i in range(2, round(sqrt(b))+1):
        if b%i == 0:
            s=0
            while b%i == 0:
                b=b//i
                s+=1
            D[i]=s
    L=[]
    for i in list(D.keys()):
        L.append(geg(n, i, i)//D[i])
    if b!=1:
        L.append(geg(n, b, b))
    m=L[0]
    for i in L:
        if m>i: m=i
    return m
print(fact(b, n))


def __starting_point():
    n, b = (int(x) for x in input().split())

    primes = dict()

    bcopy = b
    for i in range(2, int(bcopy ** 0.5) + 1):
        cnt = 0
        while bcopy % i == 0:
            bcopy //= i
            cnt += 1
        if cnt > 0:
            primes[i] = cnt
    if bcopy > 1:
        primes[bcopy] = 1
    # print(primes)

    prime___npow = {}
    count = 0
    for prime in primes:
        pw = 1
        while prime ** pw <= n:
            count += n // prime ** pw
            pw += 1
        prime___npow[prime] = count
        count = 0
    # print(prime___npow)
    MAX = 10 ** 18
    count = MAX

    for prime in primes:
        curr = prime___npow[prime] // primes[prime]
        count = min(count, curr)
    if count == MAX:
        count = 0
    print(count)
__starting_point()

n,b = list(map(int,input().split()))
if n == 1:
    print(0)
    return
a = []
x = b
i = 2
while i*i <= x:
    if x%i == 0:
        cnt = 0
        while x%i == 0:
            x //= i
            cnt += 1
        a.append([i,cnt])
    if i == 2:
        i += 1
    else:
        i += 2
if x > 1:
    a.append([x,1])

ans = 10**20

for i in a:
    lol = i[0]
    cur = i[0]
    cnt = 0
    while cur <= n:
        cnt += n//cur
        cur = cur*lol
    cnt //= i[1]
    ans = min(ans,cnt)
print(ans)    


n, b = map(int, input().split())
cnt = {}
i = 2
while i * i <= b:
    while b % i == 0:
        cnt[i] = cnt.setdefault(i, 0) + 1
        b //= i
    i += 1
if b > 1:
    cnt[b] = 1

def get(x):
    ret = 0
    d = x
    while d <= n:
        ret += n // d
        d *= x
    return ret

ans = int(1e30)
for (a, t) in cnt.items():
    ans = min(ans, get(a) // t)
print(ans)

def f(p, q, n):
    w = p
    r = 0 
    while w <= n:
        r += n // w
        w *= p
    return r // q
n,k=list(map(int, input().split()))
i = 2
s = -1
while i*i <= k:
    if k % i == 0:
        cnt = 0
        while k % i == 0:
            k //= i
            cnt += 1
        j = f(i, cnt, n)
        if s < 0 or s > j:
            s = j
    i += 1
if k > 1:
    j = f(k, 1, n)
    if s > j or s < 0:
        s = j
print(s)


n,x=list(map(int,input().split()))

import math 
L=int(math.sqrt(x))

FACT=dict()

for i in range(2,L+2):
    while x%i==0:
        FACT[i]=FACT.get(i,0)+1
        x=x//i

if x!=1:
    FACT[x]=FACT.get(x,0)+1


ANS=float("inf")
for f in FACT:
    ANS_f=0
    x=f

    while x<=n:
        ANS_f+=n//x
        x*=f

    #print(f,ANS_f)

    ANS=min(ANS,ANS_f//FACT[f])

print(ANS)

    
    


n, b = [int(x) for x in input().split()]
i = 2
ans = -1
def update(p):
    cnt = 0
    tmp = p
    while tmp<=n:
        cnt += n//tmp
        tmp *= p
    return cnt
while i*i<=b:
    if b%i==0:
        q = 0
        while b%i==0:
            b //= i
            q += 1
        cnt = update(i)
        if ans==-1:
            ans = cnt//q
        else:
            ans = min(ans,cnt//q)
    i += 1
if b>1:
    cnt = update(b)
    if ans==-1:
        ans = cnt
    else:
        ans = min(ans,cnt)
print(ans)


import time
def primeFactor(N):
    i = 2
    ret = {}
    n = N
    mrFlg = 0
    if n < 0:
        ret[-1] = 1
        n = -n
    if n == 0:
        ret[0] = 1
    while i**2 <= n:
        k = 0
        while n % i == 0:
            n //= i
            k += 1
            ret[i] = k
        if i == 2:
            i = 3
        else:
            i += 2
        if i == 101 and n >= (2**20):
            def findFactorRho(N): # Prime�łȂ����Ƃ��m�F�������̂������Ƃ���B
                def gcd(a, b):
                    if b == 0:
                        return a
                    else:
                        return gcd(b, a % b)
                def f(x, c):
                    return ((x ** 2) + c) % N
                semi = [N]
                for c in range(1, 11):
                    x=2
                    y=2
                    d=1
                    while d == 1:
                        x = f(x, c)
                        y = f(f(y, c), c)
                        d = gcd(abs(x-y), N)
                    if d != N:
                        if isPrimeMR(d):
                            return d
                        elif isPrimeMR(N//d):
                            return N//d
                        else:
                            semi.append(d)

                semi = list(set(semi))
                print (semi)
                s = min(semi)
                for i in [2,3,5,7]:
                    while True:
                        t = int(s**(1/i)+0.5)
                        if t**i == s:
                            s = t
                            if isPrimeMR(s):
                                return s
                        else:
                            break

                i = 3
                while True:
                    if s % i == 0:
                        return i
                    i += 2
                    
            while True:
                if isPrimeMR(n):
                    ret[n] = 1
                    n = 1
                    break
                else:
                    mrFlg = 1
                    j = findFactorRho(n)
                    k = 0
                    while n % j == 0:
                        n //= j
                        k += 1
                        ret[j] = k
                if n == 1:
                    break
                    
    if n > 1:
        ret[n] = 1
    if mrFlg > 0:
        def dict_sort(X):
            Y={}
            for x in sorted(X.keys()):
                Y[x] = X[x]
            return Y
        ret = dict_sort(ret)
    return ret

def isPrime(N):
    if N <= 1:
        return False
    return sum(primeFactor(N).values()) == 1

def isPrimeMR(n):
    if n == 2: return True
    if n == 1 or n & 1 == 0: return False

    d = (n - 1) >> 1
    while d & 1 == 0:
        d >>= 1

    for a in [2, 3, 5, 7, 11, 13, 17, 19, 23]:
        t = d
        y = pow(a, t, n)

        while t != n - 1 and y != 1 and y != n - 1:
            y = (y * y) % n
            t <<= 1

        if y != n - 1 and t & 1 == 0:
            return False

    return True        

def findPrime(N):
    if N < 0:
        return -1
    i = N
    while True:
        if isPrime(i):
            return i
        i += 1

def divisors(N):
    pf = primeFactor(N)
    ret = [1]
    for p in pf:
        ret_prev = ret
        ret = []
        for i in range(pf[p]+1):
            for r in ret_prev:
                ret.append(r * (p ** i))
    return sorted(ret)

n, b = list(map(int, input().split()))

# n = 10**18
# b = 2
pf = primeFactor(b)
# print(pf)

ma = 0
X = []
for i in pf:
    ma = max(ma, i ** pf[i])
    X.append([i, pf[i], 0])

mi = 10**30
for i in range(len(X)):
    j = 1
    while X[i][0]**j <= n:
        X[i][2] += n // (X[i][0]**j)
        j += 1
        
    mi = min(mi, X[i][2]//X[i][1])
    
print(mi)


n, b = map(int, input().split())
fac = []
i = 2
while i * i <= b:
    if b % i == 0:
        fac.append([i, 0])
        while b % i == 0:
            fac[-1][1] += 1
            b //= i
    i += 1

if b > 1:
    fac.append([b, 1])

ans = int(1e20)

for i in fac:
    cnt = 0
    x = i[0]
    while x <= n:
        cnt += n // x
        x *= i[0]

    ans = min(ans, cnt // i[1])

print(ans)

from sys import setrecursionlimit, stderr
from functools import reduce
from itertools import *
from collections import defaultdict, Counter
from bisect import bisect

setrecursionlimit(10**7)

def read():
  return int(input())

def reads():
  return [int(x) for x in input().split()]

def primes(n):
    sieve = [True] * (n//2)
    for i in range(3,int(n**0.5)+1,2):
        if sieve[i//2]:
            sieve[i*i//2::i] = [False] * ((n-i*i-1)//(2*i)+1)
    return [2] + [2*i+1 for i in range(1,n//2) if sieve[i]]

PRIMES = primes(10**6 + 10)

def pfact(x):
  res = Counter()
  while x > 1:
    for p in PRIMES:
      if p >= x**0.5 + 1:
        res[x] += 1
        x = 1
        break
      if x % p == 0:
        res[p] += 1
        x //= p
        break
  return res

n, b = reads()
pb = pfact(b)

ans = 1 << 63
for p, e in list(pb.items()):
  k = sum(n // (p ** i) for i in takewhile(lambda i: p ** i <= n, count(1)))
  ans = min(k // e, ans)
print(ans)


n,b=map(int,input().split())
temp=b 
pf=[]
from math import sqrt as S 
for i in range(2,int(S(b))+1):
    if b%i==0:
        c=0 
        while b%i==0:
            c+=1 
            b=b//i 
        pf.append([c,i])
if b>1:
    pf.append([1,b])
plen=len(pf)
def chk(z,p):
    ct=0 
    k=p 
    while z//k>0:
        ct+=(z//k )
        k=k*p 
    return ct 
mini=10**50
for i in range(plen):
    currp=pf[i][1]
    cnt=pf[i][0]
    cur=chk(n,currp)
    #print(cur)
    mini=min(mini,cur//cnt)
print(mini)

import math,time

facts = []
fcounts = []


def primefactors(n):
	c = 0
	if n%2 == 0:
		while n%2==0:
			c+=1
			n = n//2
		facts.append(2)
		fcounts.append(c)
	for i in range(3, (int(math.sqrt(n)+1)),2):
		c = 0
		if n % i == 0:
			while n % i == 0:
				c += 1
				n = n // i
			facts.append(i)
			fcounts.append(c)
	if n>2:
		facts.append(n)
		fcounts.append(1)

def task(x, u):
	t = 0
	p = u
	while True:
		if x<p:
			return t
		else:
			t+=(x//p)
		p*=u


n, b = list(map(int, input().split()))
primefactors(b)
l = len(facts)
val = int(1e18)
#print(facts)
#print(fcounts)
for i in range(l):
	x = facts[i]
	a = task(n,x)
	#print(a, "for value:", x)
	val = min(val, a//fcounts[i])
if val is int(1e18):
	print("0")
else:
	print(int(val))




n, b = list(map(int, input().split()))
now = 1
p = []
isp = [1] * 1000001
for i in range(2, 10 ** 6 + 1):
	if isp[i]:
		p.append(i)
	for x in p:
		if x * i > 1000000:
			break
		isp[x * i] = 0
		if i < x or i % x == 0:
			break
# print(len(p))
de = []
for prime in p:
	count = 0
	while b % prime == 0:
		b //= prime
		count += 1
	if count:
		de.append((prime, count))
	if b < prime:
		break
if b != 1:
	de.append((b, 1))
# print(de)

ans = 10 ** 20
for pair in de:
	tmp = 1
	has = 0
	num, count = pair[0], pair[1]
	while tmp <= n:
		tmp *= num
		has += n // tmp
	ans = min(ans, has // count)
print(ans)


def factorize(n):
	result = []
	N = n
	i = 2
	while i * i <= N:
		if n % i == 0:
			power = 0
			while n % i == 0:
				n = n // i
				power += 1
			result.append((i, power))
		i += 1
	if n != 1:
		result.append((n, 1))
	return result
n, b = input().split()
n = int(n)
b = int(b)
#print(n, b)
p = factorize(b)

ans = None
for (prime, power) in p:
	k = prime
	pp = 0
	while k <= n:
		pp += n // k
		k *= prime
	res = pp // power
#	print(prime, power, pp, k, res)
	if ans == None or ans > res:
		ans = res

print(ans)		 

from decimal import Decimal

list_int_input = lambda inp: list(map(int, inp.split()))
int_input = lambda inp: int(inp)
string_to_list_input = lambda inp: list(inp)

n,b=list(map(int,input().split()))
import math
facts=[]
sqt=int(math.sqrt(b))
for i in range(2,sqt+1):
    j=0
    while b%i==0:
        j+=1
        b=int(Decimal(b)/Decimal(i))
    if j>0:
        facts.append((i, j))
    if b==1:
        break
if b!=1:
    facts.append((b,1))
summ=10**18
for i in facts:
    num=i[0]
    times=i[1]
    cnt=0
    while int(n/num)!=0:
        cnt+=int(Decimal(n)/Decimal(num))
        num*=i[0]
    summ=min(summ,int(Decimal(cnt)/Decimal(times)))
print(summ)



from collections import defaultdict
def decompose(n):
    x = n
    i = 2
    fac = defaultdict(lambda: 0)
    while i*i <= n:
        while x % i == 0:
            fac[i] += 1
            x = x//i
        if x == 1:
            break
        i += 1
    if x != 1:
        fac[x] += 1
    return fac

def main():
    n, b = list(map(int, input().split()))
    # print(n, b)
    require = decompose(b)
    ans = 10**18
    for key, val in list(require.items()):
        n2 = n
        acc = 0
        while n2 > 0:
            acc += n2 // key
            n2 //= key
        ans = min(ans, acc // val)
    print(ans)

def __starting_point():
    main()

__starting_point()