#!/usr/bin/ruby
h={2=>[[2,1]],3=>[[3,1]],4=>[[2,2]],5=>[[5,1]],6=>[[2,1],[3,1]],7=>[[7,1]],8=>[[2,3]],9=>[[3,2]],10=>[[2,1],[5,1]],11=>[[11,1]],12=>[[2,2],[3,1]],13=>[[13,1]],14=>[[2,1],[7,1]],15=>[[3,1],[5,1]],16=>[[2,4]],17=>[[17,1]],18=>[[2,1],[3,2]],19=>[[19,1]],20=>[[2,2],[5,1]],21=>[[3,1],[7,1]],22=>[[2,1],[11,1]],23=>[[23,1]],24=>[[2,3],[3,1]],25=>[[5,2]],26=>[[2,1],[13,1]],27=>[[3,3]],28=>[[2,2],[7,1]],29=>[[29,1]],30=>[[2,1],[3,1],[5,1]],31=>[[31,1]],32=>[[2,5]],33=>[[3,1],[11,1]],34=>[[2,1],[17,1]],35=>[[5,1],[7,1]],36=>[[2,2],[3,2]]}
while(l=gets.split)!=["0","0\n"]	
	n=l[0].to_i;m=l[1].to_i(n)
	p h[n].map{|a,b|
		z=m;r=0
		while z>0 do r+=(z/=a) end
		r/b
	}.min
end