#!/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 z=(z/a).to_i;r+=z end
		(r/b).to_i
	}.min
end