#include<bits/stdc++.h> using namespace std; int n,s=0,ans=-1,k=0; bool f(int x){ if(x==2) return 1; for(int i=2;i<=sqrt(x);i++){ if(x%i==0) return 0; } return 1; } int main(){ cin>>n; k=n; while(f(k)!=1) k--; for(int i=1;i<=k;i++){ if(f(i)==1){ if(i==2) s=i; else ans=max((i-s)-1,ans),s=i; } } cout<<max(ans,n-k); return 0; }