class Integer def prime? n = self.abs() return true if n == 2 return false if n == 1 || n & 1 == 0 d = n-1 d >>= 1 while d & 1 == 0 20.times do a = rand(n-2) + 1 t = d y = ModMath.pow(a,t,n) while t != n-1 && y != 1 && y != n-1 y = (y * y) % n t <<= 1 end return false if y != n-1 && t & 1 == 0 end return true end end module ModMath def ModMath.pow(base, power, mod) result = 1 while power > 0 result = (result * base) % mod if power & 1 == 1 base = (base * base) % mod power >>= 1; end result end end $dx = [1, 0, -1, 0] $dy = [0, 1, 0, -1] def find(cx, cy, w) t = cy * w + cx 4.times do |i| x = cx + $dx[i] y = cy + $dy[i] t = y * w + x next if x < 0 || x >= w || y < 0 || t + 1 > $n || $b[t] return true if t + 1 == $n $b[t] = true check = find(x, y, w) $b[t] = false return true if check end return false end $n = gets.to_i $b = Array.new($n) 25.times do |j| $b[j] = (j + 1).prime? end if $n <= 25 25.times do |w| w += 1 if find(0, 0, w) puts w exit end end end if $n % 8 != 1 && !($n - 8).prime? puts 8 else puts 14 end