p (`factor #{n=gets.to_i}`.split[1..-1].map(&:to_i).select{|i|i>2}+[n%4<1?4:n]).min