import java.io.*;
import java.util.*;
import java.awt.geom.*;

/**
 * Solution to The Magical 3
 * 
 * @author vanb
 */
public class magical3_vanb
{
    public Scanner sc;
    public PrintStream ps;
        
    /**
     * Driver.
     * @throws Exception
     */
    public void doit() throws Exception
    {
        sc = new Scanner( System.in );
        ps = System.out;
        
        // We're going to need a list of primes.
        boolean isprime[] = new boolean[60000];
        Arrays.fill( isprime, true );
        isprime[0] = false;
        isprime[1] = false;
        long primes[] = new long[50000];
        int np=0;
        
        // Yeah, yeah, 4, 6 and 9 are not primes.
        // But, they are the only non-prime numbers that can be
        // an answer to this problem.
        primes[np++] = 4L;
        primes[np++] = 5L;
        primes[np++] = 6L;
        primes[np++] = 7L;
        primes[np++] = 9L;
        for( int i=2; i<isprime.length; i++ ) if( isprime[i] )
        {
            if( i>9 )primes[np++] = i;
            for( int j=i+i; j<isprime.length; j+=i )
            {
                isprime[j] = false;
            }
        }
        
        long n = sc.nextLong();
        
        // If n ends with 3 in base b, 
        // then n-3 ends in 0 in base b.
        // So, n-3 must be divisible by b.
        // We just need to find the smallest factor of n-3
        // The smallest factor has to be a prime,
        // otherwise, it would have smaller factors!
        // The exceptions are 4 and 6, which have 2 and 3 as factors,
        // which cannot be the answer because bases 2 and 3 don't have a digit 3.
        long target = n-3;
                
        // We'll only go as far as sqrt(n-3). 
        // If we can't find a factor there, then the 
        // answer is n-3 itself - sometimes. See below.
        long answer = target;
        for( int i=0; primes[i]*primes[i]<=target; i++)
        {
            if( target%primes[i]==0 )
            {
                answer = primes[i];
                break;
            }
        }
        
        // Now, this is a little weird. 
        // The target may be divisible by 2 or 3. 
        // We can't use either, since there's no digit 3 in base 2 or 3.
        // but, target/2 is a factor of target, and it's greater that sqrt(target),
        // so our loop didn't find it. Ditto for target/3.
        if( answer==target )
        {
            if( target%2==0 && target/2>3 ) answer = target/2;
            if( target%3==0 && target/3>3 ) answer = target/3;
        }
        
        ps.println( answer );
    }
    
    /**
     * @param args
     */
    public static void main( String[] args ) throws Exception
    {
        new magical3_vanb().doit();        
    }   
}