$n=<>;
$h[0]=0;
for$m(grep{!grep{$i%$_<1}2..($i=$_)-1}2..999){
	for$i(reverse $m..$n){
		$h[$i]=$h[$i-$m]+1 if defined $h[$i-$m] && $h[$i]<$h[$i-$m]+1;
	}
}
print $h[$n]||-1;