#include <fstream>
#include <cstring>
#define DIM 150010
#define INF ((1LL<<61)-1)
using namespace std;

ifstream fin ("frac.in" );
ofstream fout("frac.out");

int N, M, i, j, K, ok, minim;
int V[DIM], Back[30], P;

inline void Decomposition(long long val){
     long long val2 = val;V[0] = 0;
     for(int i = 2; i * 1LL * i <= val2 && val != 1; i ++){
          if(val % i == 0){
               V[++V[0]] = i;
               while(val % i == 0)
                    val /= i;
          }
     }
     if(val != 1)
          V[++V[0]] = val;
     return;
}

inline void CautBin(long long st, long long dr){
     while(st <= dr){
          long long mid = st + (dr - st) / 2;
          long long nr = mid;
          memset(Back, 0, sizeof(Back));
          while(Back[0] == 0){
               int i = V[0];
               int valtot = 0;
               int val = 1;
               while(Back[i] == 1)
                    Back[i--] = 0;
                    Back[i] = 1;
               if(Back[0] == 1)
                    break;
               for(i = 1; i <= V[0]; i ++){
                    if(Back[i] == 1){
                         valtot ++;
                         val *= V[i];
                    }
               }
               valtot %= 2;
               switch(valtot)
               {
                    case 1:{nr -= mid / val;break;}
                    case 0:{nr += mid / val;break;}
               }
          }
          if(nr < P)
               st = mid + 1;
          else
               dr = mid - 1;
     }
     fout << st;
     return;
}

int main(){
     fin >> N >> P;
     Decomposition(N);
     CautBin(1, 20);
     return 0;
}