require 'prime'
g=Prime.prime_division n=gets.to_i
p [3,4,g[1]&&g[1][0],g[0][0]][[n%3,n%4,n%2,0].index 0]