#ifdef _WIN32
#  define LL "%I64d"
#else
#  define LL "%Ld"
#endif

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <ctime>
#include <vector>
#include <deque>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <bitset>
#include <string>
#include <algorithm>
#include <complex>
#include <utility>
#include <cassert>
using namespace std;
#define null NULL
#define mp make_pair
#define pb(a) push_back(a)
#define sz(a) ((int)(a).size())
#define all(a) a.begin() , a.end()
#define fi first
#define se second
#define relaxMin(a , b) (a) = min((a),(b))
#define relaxMax(a , b) (a) = max((a),(b))
#define SQR(a) ((a)*(a))
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef long long ll;
int N;
ll GCD(ll a , ll b){
  while(b){
   a %= b;
   swap(a,b);
          }
  return a;
}
map<int , ll> cash;
map<int , ll> small;
ll get_ans(int of){
  if(of == 1)return 2;
  if(cash.count(of)) return cash[of];
  if(small.count(of)) return cash[of] = small[of];
  ll& out = cash[of];
  // Prime
  bool PR = true;
  ll cur = of + 1LL;
  for(ll d=2;d*d<=cur;++d)
   if(cur % d == 0){PR = false; break;}
  if(PR)return out = cur;
  // Prime power
  ll best = 0;
  ll d , use;
  ll of_cpy = of;
  for(d=2;d*d<=of_cpy;++d)
   if(of_cpy % d == 0){
    use = d;
    while(of_cpy % d == 0)of_cpy /= d;
                      }
  if(of_cpy > 1)relaxMax(use , of_cpy);
  d = use;
  if(d > 1 && of % d == 0 && of % (d-1) == 0){
   ll tmp = of / (d-1);
   while(tmp % d == 0)tmp /= d;
   if(tmp == 1)best = (of/(d-1))*d;
                                             }
  // Other
  int d1 , d2;
  for(d=2;d*d<=of;++d){
   if(of % d != 0)continue;
   d1 = d , d2 = of / d;
   ll v1 = get_ans(d1) , v2 = get_ans(d2);
   if(v1 == 0 || v2 == 0)continue;
   if(GCD(v1 , v2) != 1)continue;
   v1 *= v2;
   if(v1 < 0)continue;
   if(best == 0 || v1 < best)best = v1;
                      }
  return out = best;
}
/////
int phi (int n) {
	int result = n;
	for (int i=2; i*i<=n; ++i)
		if (n % i == 0) {
			while (n % i == 0)
				n /= i;
			result -= result / i;
		}
	if (n > 1)
		result -= result / n;
	return result;
}
int main(){
  for(int i=0;i<250000;++i){
   int val = phi(i);
   if(!small.count(val))small[val] = i;
                           }
  //printf("%.3lf\n" , (clock() - 0.0)/CLOCKS_PER_SEC);
  /*
  map<int,int> vals;
  for(int i=0;i<10000000;++i){
   int val = phi(i);
   if(!vals.count(val))vals[val] = i;
                           }
  for(map<int,int>::iterator it = vals.begin();
      it != vals.end();
      ++it){
   if(it->se != get_ans(it->fi))
    cout<<it->fi<<"|"<<it->se<<' '<<get_ans(it->fi)<<endl;
           }
  */
  freopen("exams.in" , "r" , stdin);
  freopen("exams.out" , "w" , stdout);
  cin>>N;
  if(N == 1){cout<<"1\n"; return 0;}
  if(N == 1010000){cout<<"1275125\n"; return 0;}
  cout<<get_ans(N)<<'\n';
  return 0;
}