sub f{my($x,$n,$i)=@_;$n-1?${$_**$n>$x?last:$x%$_||f($x/$_,$n-1,$i),$i++for@d[$i..$#d]}:++$%}
$_=<>;
@d=grep$X%$_<1,2..sqrt($X=/ /+$');
push@d,map$X/$_,reverse@d;
f$X,$_;print$%