require'prime';p (gets.to_i*2).prime_division.map(&:first)[1]