ll f(ll a,ll b,ll c,ll p){
	return c+=a+b?f(a/p,b/p,a%p+b%p+c>=p,p):0;
}
{
	ll@n,@k,@m,p[1d4],q[],a=Factor(m,p,q);
	wt(min[i,0,a](f(n-k,k,0,p[i])/q[i]));
}