import sys
input = sys.stdin.readline


# https://qiita.com/t_fuki/items/7cd50de54d3c5d063b4a#%E3%83%9F%E3%83%A9%E3%83%BC%E3%83%A9%E3%83%93%E3%83%B3%E7%B4%A0%E6%95%B0%E5%88%A4%E5%AE%9A%E6%B3%95%E3%81%AE%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0
def is_prime(n):
    if n == 2:  # 2であれば素数なので終了
        return 1
    if n == 1 or n%2 == 0:  # 1もしくは2より大きい偶数であれば素数でないので終了
        return 0

    m = n - 1
    lsb = m & -m  # LSB. m-1をビット列で表した時立っているビットのうち最も小さいもの
    s = lsb.bit_length()-1  # 上述のs. LSB以上のビットの部分をdとし、2^s = LSBとすると上述のp-1 = 2^sdを満たす
    d = m // lsb

    test_numbers = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]

    for a in test_numbers:
        if a == n:  # a = n -> 任意の自然数kについてa^k ≡ 0(mod n)なので無視
            continue
        x = pow(a,d,n)  # x ≡ a^d(mod n)で初期化
        r = 0
        if x == 1:  # a^d ≡ 1(mod n)なので無視
            continue
        while x != m:  # r = 0からsまで順にx ≡ a^(2^rd) ≡ -1(mod n)を検証
            x = pow(x,2,n)
            r += 1
            if x == 1 or r == s:  # x ≡ 1(mod n) -> x^2 ≡ 1(mod n)で-1になり得ないので合成数
                return 0
    return 1  # すべてのテストを通過したら素数であるとして終了

x=10**6   

L=1000

Primelist=[i for i in range(x+1)]
Primelist[1]=0 # 1は素数でないので0にする.
 
for i in Primelist:
    if i>L:
        break
    if i==0:
        continue
    for j in range(2*i,x+1,i):
        Primelist[j]=0

Primes=[Primelist[j] for j in range(x+1) if Primelist[j]!=0]

SP=set(Primes)

N=int(input())

if N<=10**6:
    for w in range(1,N+1):
        h=(N+w-1)//w

        MAP=[[0]*w for i in range(h)]
        MAP[0][0]=1
        Q=[(0,0)]
        r=N%w
        if r==0:
            r=w

        while Q:
            x,y=Q.pop()

            for z0,w0 in [(x+1,y),(x-1,y),(x,y+1),(x,y-1)]:
                if 0<=z0<h and 0<=w0<w:
                    if z0!=h-1:
                        if (z0*w+w0+1) in SP:
                            continue
                        else:
                            if MAP[z0][w0]==0:
                                MAP[z0][w0]=1
                                Q.append((z0,w0))
                    else:
                        if 0<=w0<r:
                            if (z0*w+w0+1) in SP:
                                continue
                            else:
                                if MAP[z0][w0]==0:
                                    MAP[z0][w0]=1
                                    Q.append((z0,w0))

        if MAP[h-1][r-1]==1:
            print(w)
            break
                            

else:
    if N%8==1 and is_prime(N-8):
        print(14)
    else:
        print(8)