#!/usr/bin/ruby
require 'mathn'
while(l=gets.split)!=["0","0"]	
	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=z.div a) end
		r.div b
	}.min
end