require 'prime'
loop {
    n, m = gets.split
    n = n.to_i
    break if n == 0
    m = m.to_i(n)  
    a = []
    Prime.prime_division(n).each{|q, k|
        l = 0
        f = q
        while f <= m
            l += m / f
            f *= q 
        end
        a << l / k
    }
    p a.min
} 