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