#!/usr/bin/ruby
require 'mathn'
h={};2.step(36){|i|h[i]=i.prime_division}
while(l=gets.split)!=["0","0"]	
	n=l[0].to_i;m=l[1].to_i(n)
	if n==0 then break end
	x=99999999
	h[n].each{|a,b|
		z=m;r=0
		while z>0 do r+=(z=z.div a) end
		if x>r.div(b) then x=r.div(b) end
	}
	p x
end