// Example program
#include <iostream>
#include <string>

using namespace std;

long long bin;

long long euler_phi(long long n) {
  long long ans = n;
  for (long i = 2; i * i <= n; i++)
    if (n % i == 0) {
      ans = ans / i * (i - 1);
      while (n % i == 0) n /= i;
    }
  if (n > 1) ans = ans / n * (n - 1);
  return ans;
}

long long gcd(long long a, long long b) {
  long long i = __builtin_ctz(a);
  long long j = __builtin_ctz(b);
  long long k = min(i, j);
  long long d;
  b >>= j;
  while (a) {
    a >>= i;
    d = b - a;
    i = __builtin_ctz(d);
    if (a < b) b = a;
    if (d < 0) a = -d;
    else a = d;
  }
  return b << k;
}

long long lcm(long long a, long long b){
    return a*b/gcd(a,b);
}

long long quickpow(long long a, long long b, long long m) {
    a %= m;
    b %= bin;
   long long sum = 1;
   while (b > 0) {
       if (b & 1)
           sum = sum * a % m;
       a = a * a % m;
       b >>= 1;
   }
   return sum;
}

bool is_ok(long long n){
    bin = euler_phi(n);
    long long MAX = lcm(n,bin);
    for(int i = 1; i < MAX; i++){
        if(gcd(i,n)==1){
            if((quickpow(i,i,n)-1 % n == 0) && ((i-1)%n!=0)){
                cout << i << endl;
                return 0;
            }
        }
    }
    cout<<"pass"<<endl;
    return 1;
}

int main()
{

  long long k;
  cin>>k;
  is_ok(k);
  main();
  
  /*
  for(int i = 1; i < 1000; i++){
      if(is_ok(2*i)){cout << 2*i << " ";}
    }
    */
  return 0;
}