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