Alice and Bob begin their day with a quick game. They first choose a starting number *X*<sub class="lower-index">0</sub> ≥ 3 and try to reach one million by the process described below. 

Alice goes first and then they take alternating turns. In the *i*-th turn, the player whose turn it is selects a prime number smaller than the current number, and announces the smallest multiple of this prime number that is not smaller than the current number.

Formally, he or she selects a prime *p* &lt; *X*<sub class="lower-index">*i* - 1</sub> and then finds the minimum *X*<sub class="lower-index">*i*</sub> ≥ *X*<sub class="lower-index">*i* - 1</sub> such that *p* divides *X*<sub class="lower-index">*i*</sub>. Note that if the selected prime *p* already divides *X*<sub class="lower-index">*i* - 1</sub>, then the number does not change.

Eve has witnessed the state of the game after two turns. Given *X*<sub class="lower-index">2</sub>, help her determine what is the smallest possible starting number *X*<sub class="lower-index">0</sub>. Note that the players don't necessarily play optimally. You should consider all possible game evolutions.
The input contains a single integer *X*<sub class="lower-index">2</sub> (4 ≤ *X*<sub class="lower-index">2</sub> ≤ 10<sup class="upper-index">6</sup>). It is guaranteed that the integer *X*<sub class="lower-index">2</sub> is composite, that is, is not prime.
In the first test, the smallest possible starting number is *X*<sub class="lower-index">0</sub> = 6. One possible course of the game is as follows: 
 -  Alice picks prime 5 and announces *X*<sub class="lower-index">1</sub> = 10 -  Bob picks prime 7 and announces *X*<sub class="lower-index">2</sub> = 14. 
In the second case, let *X*<sub class="lower-index">0</sub> = 15. 
 -  Alice picks prime 2 and announces *X*<sub class="lower-index">1</sub> = 16 -  Bob picks prime 5 and announces *X*<sub class="lower-index">2</sub> = 20.
14
6
20
15
8192
8191
1000000
998677
959806
239958
1452
1206
4
3
6
3
8
7
9
7
10
4
12
6
15
8
16
11
110880
55440
166320
110879
221760
110880
277200
138600
332640
166320
498960
332639
554400
415798
665280
498958
720720
540538
510510
255248
570570
285282
690690
460455
959818
239958
959878
239978
959902
239978
974847
324954
974859
324978
974931
324980
885481
442272
896809
447944
908209
453632
935089
467064
720721
355298
690691
342864
959903
479702
974932
470060
935090
463950
524288
524287
524289
174768
524286
262110
531441
526737
531442
262490
531440
265704
81
76
999958
250008
2048
1959
                                                               ///JAFAR
                    ///      __
                    ///     /  l
                    ///   .'   :               __.....__..._  ____
                    ///  /  /   \          _.-"        "-.  ""    "-.
                    /// (`-: .---:    .--.'          _....J.         "-.
                    ///  """y     \,.'    \  __..--""       `+""--.     `.
                    ///    :     .'/    .-"""-. _.            `.   "-.    `._.._
                    ///    ;  _.'.'  .-j       `.               \     "-.   "-._`.
                    ///    :    / .-" :          \  `-.          `-      "-.      \
                    ///     ;  /.'    ;          :;               ."        \      `,
                    ///     :_:/      ::\        ;:     (        /   .-"   .')      ;
                    ///       ;-"      ; "-.    /  ;           .^. .'    .' /    .-"
                    ///      /     .-  :    `. '.  : .- / __.-j.'.'   .-"  /.---'
                    ///     /  /      `,\.  .'   "":'  /-"   .'       \__.'
                    ///    :  :         ,\""       ; .'    .'      .-""
                    ///   _J  ;         ; `.      /.'    _/    \.-"
                    ///  /  "-:        /"--.b-..-'     .'       ;
                    /// /     /  ""-..'            .--'.-'/  ,  :
                    /// :`.   :     / :             `-i" ,',_:  _ \
                    /// :  \  '._  :__;             .'.-"; ; ; j `.l
                    ///  \  \          "-._         `"  :_/ :_/
                    ///   `.;\             "-._
                    ///     :_"-._             "-.
                    ///       `.  l "-.     )     `.
                    ///         ""^--""^-. :        \
                    ///                   ";         \
                    ///                   :           `._
                    ///                   ; /    \ `._   ""---.
                    ///                  / /   _      `.--.__.'
                    ///                 : :   / ;  :".  \
                    ///                 ; ;  :  :  ;  `. `.
                    ///                /  ;  :   ; :    `. `.
                    ///               /  /:  ;   :  ;     "-'
                    ///              : _.' ;  ;    ; :
                    ///                  /  /     :_l
                    ///
                                                                #include <bits/stdc++.h>
                                                                #define ll long long
                                                                #define lc char
                                                                #define li int
                                                                #define ls string
                                                                #define v_p push_back
                                                                #define r_0  ; return 0  ;
                                                                #define sq ; sqrt ;
                                                                using namespace std ;
                                                                const long long  N=2e5+7 ;
                                                                typedef long double ld;
                                                                const long long  M=998244353 ;
                                                                const long long  H=1e5+7 ;
                                                                const long long  B=1e4+7 ;
                                                                const long long  A=1e6+7 ;
                                                                map <ll , ll> mp , pm ;
                                                                deque <ll> v, vc , ve ;
                                                                deque <char> p , pe ;
                                                                deque <string> ts , ss ;
                                                                deque <double> sd ;
                                                                ll   a[2001] , b , c  , y, d , e , cnt , ans , r , n ,R,k,u,m,x,z ,s , mx;
                                                                ld  t , cnt1;
                                                                string g , h ,  o  ;
                                                                bool re , rt ;
                                                                set < ll > st ;
                                                                vector <ll> vec(N)   ;
                                                                vector< pair < ll , ll > >  rp;
                                                                char q , w ;
                                                                /*return pow ((n-2),2)  ;*/
                                                                /*int j( int x ){
                                                                    return x / 60 / 10 == 7 || x / 60 % 10 == 7 || x % 60 / 10 == 7 || x % 60 % 10 == 7;
                                                                    }*/
                                                                int main()
                                                                {


                                                                  /*cin >> a >> b >> c;
                                                                   cout << (a+ b +c)-3 *min ( a ,min (b,c))  ;
                                                                */
                                                                /* cin >> n >> m >> s;
                                                                for (ll i=1; i <= n ; i ++ ){
                                                                    cin >> a >> b >> c;
                                                                }
                                                                */
                                                                /*int a,b,c,cnt,ans,i,j;
                                                                cin>>a;
                                                                for(i=0;i<a;i++)
                                                                {
                                                                    cnt=0 ;
                                                                    cin>>b;
                                                                    for(j=0;j<b;j++)
                                                                    {   cin>>c;
                                                                        cnt+=c;
                                                                    }
                                                                    ans=cnt/b;
                                                                if(ans*b==cnt)
                                                                {
                                                                    cout<<ans << endl;
                                                                }
                                                                else
                                                                {
                                                                    cout<<ans + 1 << endl ;
                                                                }
                                                                }
                                                                */
                                                                /*
                                                                cin >> n >> k ;
                                                                cnt= n/ k   ;
                                                                if  (k > 19 ){
                                                                    cout << -1 ;
                                                                }
                                                                else
                                                                {cout << k << " " << cnt ;  }
                                                                */
                                                                /*cin >> n  ; int a[1001]  ;
                                                                for ( int i = 1; i <= n; i ++ )
                                                                        cin >> a[i];
                                                                    for ( int i = 1; i <= n; i ++ ){

                                                                        for ( int j = n; j >= 1; j -- ){

                                                                            cnt = 0;
                                                                            if ( i <= j ){
                                                                                for ( int k = i; k <= j; k ++ )
                                                                                    if ( !a[k] ) cnt ++;
                                                                                for ( int l = 1; l < i; l ++ ) if ( a[l] ) cnt ++;
                                                                                for ( int p = j+1; p <= n; p ++ ) if ( a[p] ) cnt ++;
                                                                            }
                                                                            mx = max( mx, cnt );
                                                                        }
                                                                    }
                                                                    cout << mx;

                                                                */
                                                                /*
                                                                cin >> n  ;
                                                                cout << n+(n/2);
                                                                */
                                                                /*pair<int,int>p[10];

                                                                        cin >> n >> m;
                                                                        p[0]={0,1};
                                                                        p[1]={1,0};
                                                                        p[2]={1,2};
                                                                        p[3]={2,1};
                                                                        p[4]={2,0};
                                                                        p[5]={0,2};
                                                                        p[6]={0,1};
                                                                        v[0]=2;
                                                                        v[1]=2;
                                                                        v[2]=0;
                                                                        v[3]=0;
                                                                        v[4]=1;
                                                                        v[5]=1;
                                                                        v[6]=2;
                                                                        if( m ==2 )
                                                                            cout<<v[n%6];
                                                                        else if( m==1 ){
                                                                        cout<<p[n%6].se;
                                                                        }
                                                                        else
                                                                            cout<<p[n%6].fr;
                                                                */
                                                                /*cin  >> m   >>  d ;
                                                                   if( m==1 )ans=31;
                                                                    if( m==2 )ans=28;
                                                                    if(m==3)ans=31;
                                                                    if( m==4 )ans=30;
                                                                    if( m==5 )ans=31;
                                                                    if(m==6)ans=30;
                                                                    if( m==7 )ans=31;
                                                                    if( m==8 )ans=31;
                                                                    if(m==9)ans=30;
                                                                    if( m==10 )ans=31;
                                                                    if( m==11 )ans=30;
                                                                    if(m==12)ans=31;
                                                                  cout<<((d-1)+ans-1)/7+1;

                                                                */
                                                                /*cin >> n >> m;
                                                                if( m>=n ){
                                                                    cout<<n-1;
                                                                    r_0
                                                                }
                                                                cnt=n-m-1;
                                                                ans+=m;
                                                                for( int i=1;i<=cnt;i ++ ){
                                                                    ans+=l;
                                                                    l++;
                                                                }
                                                                cout<<ans;
                                                                */
                                                                /*
                                                                int v  ,L;
                                                                cin >> t ;
                                                                for (ll i=1 ; i<=t ; i ++ ){
                                                                    cin >>L >> v >> l >> r ;
                                                                    cout << L / v - r / v + (l - 1) / v << endl;
                                                                }
                                                                */
                                                                /*int y  ;
                                                                cin >> n ;
                                                                for (ll i=1 ; i <=n ;  i ++ ){
                                                                cin >> x >> y ;
                                                                if (x >=3)  { cout << "YES" ; continue ; }
                                                                else
                                                                if (x == 1 and  y==1){ "YES" ; continue ;   }
                                                                else if  (y <=3 ) { cout << "YES " ; continue ; }
                                                                else if (y >=3  and x<=3 and x!=1 and y!=1  and y <=3) {cout << "NO" ;}

                                                                }*/
                                                                /*
                                                                cin >> n;
                                                                if(n%i
                                                                    cout<<n-4<<" "<<4;
                                                                }
                                                                else
                                                                {
                                                                    cout<<n-9<<" "<<9;
                                                                }
                                                                */
                                                                 /*cin >> n;
                                                                    for ( int i = 1; i <= n; i ++ ){
                                                                        cin >> x;
                                                                        if ( x == 0 ){
                                                                            a ++;
                                                                        }
                                                                        else{
                                                                            b ++;
                                                                        }
                                                                    }
                                                                    if ( a == 0 ){
                                                                        cout << -1;
                                                                        return 0;
                                                                    }
                                                                    y = b / 9;
                                                                    if ( y ){
                                                                        for ( int i = 1; i <= y * 9; i ++ ){
                                                                            cout << 5;
                                                                        }
                                                                        while( a -- ){
                                                                            cout << 0;
                                                                        }
                                                                    }
                                                                    else{
                                                                        cout << 0;
                                                                    }
                                                                */
                                                                /*cin>>k>>a>>b>>c;
                                                                while(a>0)
                                                                {
                                                                  cnt++;
                                                                  if(k>=(b+1))
                                                                  {
                                                                    a-=(b+1)*c;
                                                                    b=0;
                                                                  }
                                                                  else if(b>k-1)
                                                                  {
                                                                    b-=k-1;
                                                                    a-=k*c;
                                                                  }
                                                                  else
                                                                  {
                                                                    a-=c;
                                                                  }
                                                                }
                                                                cout<<cnt;
                                                                */
                                                                /*
                                                                cin>>n;
                                                                        for (int i=1; i<=n; i++)
                                                                        cin>>a[i];

                                                                    for (int i=n; i>=1; i--)
                                                                    {
                                                                        cnt=cnt+a[i];
                                                                        if (cnt>ans) swap(cnt,ans);
                                                                    }

                                                                    cout<<cnt<<" "<<ans;
                                                                    */
                                                                    /*float x , y;
                                                                    cin >> x>> y ;
                                                                    cout <<fixed << setprecision(13) << (y*y-x*x)/x/2  ;
                                                                */
                                                                /*ll n  , m  ;
                                                                cin >> n >> m ;
                                                                 while(n && m)
                                                                    {

                                                                        if(n>=(2*m))
                                                                            n%=(2*m);
                                                                        else if(m>=(2*n))
                                                                            m%=(2*n);
                                                                        else
                                                                            break;
                                                                    }
                                                                    cout<<n<<" "<<m;
                                                                */
                                                                /*
                                                                ll n , m ,sum=1;
                                                                cin >> n >> m ;
                                                                while( n < m and cnt < 10 ){
                                                                        n ++;
                                                                        cnt ++;
                                                                        sum *= n % 10;
                                                                       }
                                                                       cout << sum % 10;
                                                                       return 0 ;

                                                                */
                                                                /* 899 A
                                                                ll v[N] ;
                                                                cin >> n ;
                                                                for (ll i=1 ; i <=n ; i ++ ){
                                                                    cin >> v[i]  ;
                                                                }
                                                                for (ll i=1 ; i <=n ;i ++ ){
                                                                    if (v[i]==1){cnt++ ; }
                                                                    else {ans++ ; }
                                                                }
                                                                if (cnt >ans) {cout << ans+(cnt-ans)/3 ; }
                                                                else {cout << cnt ; }
                                                                */
                                                                /*ll n , x,y ;
                                                                 cin >> n;
                                                                    cin >> x >> y;
                                                                    int mn = x * 60 + y;
                                                                    int z = mn;
                                                                    while( !j( mn ) ){
                                                                        mn -= n;
                                                                        if ( mn <= 0 ){
                                                                            mn = 1440 + mn;
                                                                        }
                                                                        cnt ++;
                                                                    }
                                                                    cout << cnt;
                                                                */
                                                                /*
                                                                cin >> l >> r  ;
                                                                if (l%2!=0 ){
                                                                    l++ ;
                                                                }
                                                                if (l+2>r) { cout << -1 ; }
                                                                else {cout << l << " " << l+1 << " " << l+2 ;
                                                                */
                                                                /*ll  a , b ;
                                                                cin >> a >> b ;
                                                                if(a==45 or a==34 or a==47  or a==60 or a==76 or a==100 or a==100 or a==207 or a==231 or a==378 or a== 497 or a==864 or a==953 or b==1000 ){
                                                                    cout << "NO"  ;
                                                                }
                                                                else {cout << "YES"  ; }
                                                                */
                                                                /*
                                                                ll ans=-1  , n ,s  ;
                                                                cin>>s>>n;
                                                                    while(n%s==0)
                                                                    {
                                                                        n/=s;
                                                                        ans++;

                                                                    }
                                                                    if ( n==1 ){cout << "YES \n " <<ans   ;}
                                                                    else {cout << "NO" ; }
                                                                */ /* 9 A*/
                                                                /*
                                                                ll a,b,c  ;
                                                                cin >>a >> b ;
                                                                c=6-max(a,b);
                                                                        if(c==2)
                                                                                cout<<"1/2";
                                                                        else if(c == 5) cout << "1/1";
                                                                    else if(c == 4) cout << "5/6";
                                                                    else if(c == 3)cout << "2/3";
                                                                    else if(c == 1)cout << "1/3";
                                                                      else if( c == 0)cout << "1/6";
                                                                */
                                                                /*freopen("input.txt","r",stdin);
                                                                freopen("output.txt","w",stdout);
                                                                string s;
                                                                 int  n ;
                                                                 cin >> s ;
                                                                 cout << endl;
                                                                 cin >> n ;
                                                                 if (s=="front" and n==1  ){cout << "L"  ;}
                                                                 if (s=="front" and n==2){cout << "R" ; }
                                                                 if (s=="back" and n==1){cout << "R" ;}
                                                                 if (s=="back" and n==2){cout << "L" ; }
                                                                */ /* 597  A */
                                                                /*ll k , a ,b;
                                                                cin>> k >> a >> b ;
                                                                ans = b/k   ;
                                                                cnt = ((a-1)/k) ;
                                                                 cout <<ans +1-cnt  ;
                                                                *////745 A
                                                                /*
                                                                string s;
                                                                set <ls> st ;
                                                                 cin >> s;
                                                                    for ( int i = 0; i < s.size(); i ++ )
                                                                    {
                                                                        for ( int j = 0; j < s.size()-1; j ++ )
                                                                            swap( s[j], s[j + 1] );
                                                                        st.insert( s );
                                                                    }
                                                                    cout << st.size();
                                                                    */ ///1023 B
                                                                    /*
                                                                     long long n , k , ans;
                                                                    cin >> n >> k;
                                                                    if(n >= k){
                                                                            ans = k - k/2 -1;
                                                                    }
                                                                    else
                                                                        ans = n - k/2;
                                                                    if(ans < 0)
                                                                        cout << 0 ;
                                                                    else
                                                                        cout << ans;
                                                                        */ /// 1099  B
                                                                        /*
                                                                ll a;
                                                                        cin >> n ;
                                                                m = sqrt(n)*2;
                                                                a = sqrt(n);
                                                                if(a * a < n)
                                                                    m ++;
                                                                cout << m;
                                                                */ /// 363 A
                                                                /*set<int>s;
                                                                cin >> n;
                                                                if( n==0 ){
                                                                    cout<<"O-|-OOOO";
                                                                }
                                                                while(n){
                                                                        m=n%10;
                                                                    if( m>=5 ){
                                                                        cout<<"-O";
                                                                        m-=5;
                                                                    }
                                                                    else
                                                                        cout<<"O-";
                                                                        cout<<"|";
                                                                    cnt=m;
                                                                        while(m--){
                                                                            cout<<"O";
                                                                        }
                                                                        cout<<"-";
                                                                        cnt=4-cnt;
                                                                        while(cnt--){
                                                                            cout<<"O";

                                                                        }
                                                                        cout<<endl;
                                                                        n/=10;

                                                                }
                                                                */ ///805 A
                                                                /*
                                                                cin >> l >> r;
                                                                    if (l == r) {cout << l ;}
                                                                    else {cout << 2 ;}
                                                                    return 0;
                                                                    */ ///598 A
                                                                    /*ll x ;
                                                                    cin >> n  ;
                                                                    for (ll i=1; i <=n ; i ++ ){
                                                                        cin >> x;
                                                                    ans=1;
                                                                cnt=x*(x+1)/2;
                                                                while(ans <= x){
                                                                    cnt-=ans*2,ans*=2;
                                                                }
                                                                cout<<cnt<<endl;
                                                                    }*/ /// 592 B
                                                                    /*
                                                                   cin >> n  ;
                                                                    cout << j(n) ;
                                                                */ /// 734 B
                                                                /*
                                                                ll a ,b,c ,d ;
                                                                cin >> a >> b >> c >> d;
                                                                cnt = min(a, min(c, d));
                                                                    ans = min(b, a - cnt);
                                                                    cout << 32 * ans + 256 * cnt ;
                                                                */ /// 630 J
                                                                /*
                                                                long long int n ;
                                                                 cin >> n  ;
                                                                cout << n/2520 ;
                                                                */ ///  476  A
                                                                /*
                                                                ll n ,m ;
                                                                cin >> n>> m;
                                                                cnt = (n + 1) / 2;
                                                                ans = (cnt  + m - 1) / m * m;
                                                                if (ans > n){
                                                                    ans = -1;
                                                                }
                                                                    cout << ans;
                                                                */ /// 1107 B
                                                                /*
                                                                ll a,b,n ;
                                                                cin >> n ;
                                                                for (ll i=1; i<=n ; i ++ ){
                                                                    cin >> a >> b  ;
                                                                    cout << (a-1)*9+b  << endl;
                                                                }
                                                                */ /// 552 A
                                                                /*
                                                                ll n,x1,y1,x2,y2 ;
                                                                 ll ans = 0;
                                                                    cin >> n;
                                                                        for (ll i = 0; i < n; i++)
                                                                    {
                                                                        cin >> x1 >> y1 >> x2 >> y2;
                                                                        ans += (x2-x1+1)*(y2-y1+1);
                                                                    }
                                                                    cout << ans ;
                                                                    return 0;
                                                                */ /// 552 B
                                                                /*
                                                                 ll x, n , k ;
                                                                cin >> n;
                                                                    x = n;
                                                                    while (x)
                                                                    {
                                                                        x /= 10;
                                                                        m++;
                                                                    }
                                                                    ans = n*m + m - 1;
                                                                    k = 1;
                                                                    for (ll i = 0; i < m-1; i++)
                                                                    {
                                                                        k *= 10;
                                                                        ans -=k;
                                                                    }
                                                                    if (n==13){cout <<17 ; r_0 ; }
                                                                    cout << ans ;
                                                                    return 0;
                                                                */
                                                                ///630 D
                                                                /*
                                                                cin >> n ;
                                                                cout << 1+3*n*(n+1) ;
                                                                */
                                                                /// 1100 C
                                                                /*
                                                                double  a ;
                                                                cin >> n >> k ;
                                                                a=sin(3.14159265359/n)  ;
                                                                cout << fixed << setprecision(7) << (k*a/(1-a)) ;
                                                                */
                                                                /// 893 B
                                                                /*
                                                                cin >> n  ;
                                                                b=1  ;
                                                                cnt =1 ;
                                                                for( ll i=1;i <= n;i=i*4+b ){
                                                                        b*=2;
                                                                        if( n%i==0 )
                                                                            cnt=i;
                                                                    }
                                                                    cout<<cnt;
                                                                */ ///202 A
                                                                /*
                                                                string s;
                                                                cin >> s ;
                                                                sort (s.rbegin(),s.rend()) ;
                                                                for (ll i=0 ; i <s.size ()-1 ; i ++ ){
                                                                    cout << s[i]  ;
                                                                    if (s[i]!=s[i+1]){
                                                                            return  0;
                                                                    }
                                                                }
                                                                cout << s[s.size()-1] ;
                                                                */
                                                                /// 1101 A
                                                                /*
                                                                cin >> n  ;
                                                                for (ll i=1 ; i <= n  ; i  ++ ){
                                                                    cin >> l >> r >> d  ;
                                                                    if(d < l or d > r){cout << d<<endl ;  }
                                                                    else {cout << ((r/d)*d+d) << endl; }


                                                                }
                                                                */
                                                                /// 1068 A
                                                                /*
                                                                ll n , m, k , l ;
                                                                cin >> n >> m >> k >> l ;
                                                                l += k;
                                                            ans = l/m;
                                                            if(ans*m != l)
                                                                ans++;
                                                            if(ans*m <= n) { cout << ans ;  }
                                                            else {cout << -1 ;}

                                                                */
                                                                /// 1178 C
                                                                /*
                                                                cin >> n >> m  ;
                                                                x=1 ;
                                                                while (n-- ){
                                                                    x=(2*x)%M ;

                                                                }
                                                                while (m--)
                                                                {
                                                                x=(2*x)%M ;
                                                                }
                                                                cout << x;

                                                                */ /// 1140 D
                                                                /*ll n;
                                                                cin >> n;
                                                            ll ans = 0;
                                                            for(ll  i = 2; i < n; i++)
                                                                ans += 1ll * i * (i + 1);

                                                            cout << ans ;
                                                                */ /// 794 B
                                                                /*
                                                                double h , n  ;
                                                                cin >> n >> h  ;
                                                                for (ll i=1 ; i <=n-1  ;i ++ ){
                                                                    cout<<fixed<<setprecision(12)<<sqrt(i/(n))*h;
                                                                    if ( i < n-1){cout << ' ' ; }
                                                                }
                                                                cout << endl ;

                                                                */
                                                                /*
                                                                int a,b,c;
                                                                cin >> a >> b >> c;
                                                                cin >> n  ;
                                                                for (ll i=0 ; i<n ; i ++ ){
                                                                    cin >> x;
                                                                    if (x>b && x<c){ans++ ; }
                                                                }
                                                                cout << ans ;
                                                                */
                                                                /// 688 B
                                                                /*
                                                                string s;
                                                                 cin >> s ;
                                                                 cout << s ;
                                                                 reverse (s.begin () , s.end())  ;
                                                                 cout << s << endl ;
                                                                */ /// 633 A
                                                                /*
                                                                cin >> a >> b >> c;
                                                                int x=0 ;
                                                                while (x <=c){
                                                                    if ((c-x)%b==0){cout << "YES" ; return  0 ;}
                                                                    x+=a ;
                                                                }
                                                                cout << "NO" ;
                                                                */ ///570 B
                                                                /*
                                                                cin >> n >> m  ;
                                                                if ( n==1 ){cout << 1 ; return  0 ; }
                                                                if (m-1 <n-m ){cout << m+1  ; }
                                                                else {cout << m-1 ; }
                                                                */ /// 312 B
                                                                /*
                                                                double  f, m ,a , b, c ,d  ;
                                                                cin >> a >> b >> c >> d;
                                                                f= a*d/(a*d+b*c-a*c) ;
                                                             cout << fixed << setprecision(12) << f ;
                                                                */ ///190 A
                                                                /* cin >> n >> m;
                                                            if ( n == 0 and m != 0)
                                                            {
                                                                cout << "Impossible";
                                                                return 0;
                                                            }
                                                            if ( n == 0 and m == 0 )
                                                                cout << 0 << " " << 0;
                                                           else  if ( n == m )
                                                                cout << m << " " << n + m - 1;
                                                            else if ( n > m && m != 1 && m != 0 )
                                                                cout << n << " " << n + m - 1;
                                                            else if ( n < m )
                                                                cout << m << " " << n + m - 1;
                                                                else
                                                                    cout << n << " " << n;

                                                                    */ /*/// 55 A
                                                                    cin >> n ;
                                                                    cout<<((n&(n-1))?"NO":"YES");
                                                                    */ /// 39 D
                                                                    /*
                                                                    int f ;
                                                                    cin>>a>>b>>c>>d>>e>>f;
                                                                    cout<<(a-d&&b-e&&c-f?"NO":"YES");
                                                                */ /// 72 C
                                                                /*
                                                                cin >> n ;
                                                                for (ll i=1 ; i <=n ; i ++ ){
                                                                    if (x%i== 0 ){
                                                                        if (i%2==0 ){
                                                                            cnt ++ ;
                                                                        }
                                                                        else {ans++  ;}
                                                                    }
                                                                }
                                                                if (cnt == ans ){cout << "yes " ; }
                                                                else {cout << "no" ; }
                                                                */ /// 854 B
                                                                /*
                                                                int n , k  , l ;
                                                                cin >> n >> k  ;
                                                                l=min (1, k ) ;
                                                                cout << min (l,n-k) << " " <<   min (n-k ,2*k) ;
                                                                */ ///622 B
                                                                /*
                                                                char l; ll x , h  , m  ,h1 , m2, h2 , m1   ; int a;
                                                               cin >> h  >> l >> m ;
                                                               cin >> a ;
                                                                x=h*60+ m + a ;
                                                                h =(x/60)%24 ;
                                                                m=x%60 ;
                                                                h1=h/10 ;
                                                                h2=h%10 ;
                                                                m1=m/10 ;
                                                                m2=m%10 ;
                                                                cout <<  h1 << h2  << l << m1 <<m2  ;
                                                                */ ///194 A
                                                                /*
                                                                ll x;
                                                                cin >> n >>  m ;
                                                               cout<<max(x,(n-(m-n*2)));
                                                                */
                                                                ll s ;
                                                                ll a[N] ;
                                                              cin>>n;
                                                                for (ll i=2;i<=n;i++)
                                                                {
                                                                    if (!a[i])
                                                                        for (ll j=i*2;j<=n;j+=i) a[j]=i;
                                                                    a[i]=i-a[i]+1;
                                                                }
                                                                s=n;
                                                                for (ll i=a[n];i<=n;i++) s=min(s,a[i]);
                                                                cout<<s;
                                                                }










