#include <iostream>
#include <fstream>
#include <bitset>
using namespace std;
ifstream f("frac.in");
ofstream g("frac.out");
long long pr[100000],divvv[100000],nn,pp;
int nr1=0,sol[100],nr;
bitset <1000001> x;
void ciurprimi()
  {
    int i,nr,j;
    for(i=2;i<=1000000;i++)
       x[i]=1;
    for(i=2;i<=1000;i++)
      {
          if(x[i]==1)
                for(j=i*i;j<=1000000;j=j+i)
                   x[j]=0;
      }
    nr=0;
    for(i=2;i<=1000000;i++)
      if(x[i]==1)
        {
            nr++;
            pr[nr]=i;
        }
      i=1;
      long long z;
      f>>nn;
      z=nn;
      while(i<=nr && (long long)pr[i]*pr[i]<=z)
         {
             if(z%pr[i]==0)
               {
                   nr1++;
                   divvv[nr1]=pr[i];
                   while(z%pr[i]==0)
                      z=z/pr[i];
               }
            i++;
         }
      if(z>1)
       {
           nr1++;
           divvv[nr1]=z;
       }
  }
void modi(long long n,long long mm,long long poz,long long &sumi,long long aux)
  {
     long long p=1;
     for(long long k=1;k<=mm;k++)
            p=p*divvv[sol[k]];
     if(mm%2==0)
        p=-p;
     sumi=sumi+aux/p;
  }
void bkt(long long n,long long mm,long long poz,long long &sumi,long long aux)
  {
      if(poz==mm+1)
         modi(n,mm,poz,sumi,aux);
         else
         {
             for(long long b=1;b<=n;b++)
               {
                 int ok=1;
                 for(long long c=1;c<poz;c++)
                      if(sol[c]==b)
                         ok=0;
                 if(ok==1  && sol[poz-1]<b)
                    {
                      sol[poz]=b;
                      bkt(n,mm,poz+1,sumi,aux);
                    }
               }
         }
  }
long long final(long long aux)
  {
      long long huh,suma=0;
      for(int h=1;h<=nr1;h++)
            {
               huh=0;
               bkt(nr1,h,1,huh,aux);
               suma=suma+huh;
            }
      return aux-suma;

  }
long long cautbin()
  {
      long long i,pos;
      pos=(long long)1<<61;
      for(i=0;pos!=0;pos=pos/2)
        if(final(i+pos)<=pp-1)
           i=i+pos;
      return i+1;
  }
int main()
{
    ciurprimi();
    f>>pp;
    g<<cautbin();
    f.close();
    g.close();
}