#!/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.chomp)!="0 0"
	l=l.split
	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=z.div(a)) end
		r.div(b)
	}.min
end