#!/usr/bin/ruby
require 'prime'
while true
	l=gets.split
	n=l[0].to_i;m=l[1].to_i(n)
	if n==0 then break end
	p n.prime_division.map{|a,b|
		z=m
		r=0
		while z>0 do
			r+=(z/=a)
		end
		r/b
	}.min
end