#include<iostream>
#include<fstream>
#include<bitset>
using namespace std;

#define NMAX 1000001

bitset <NMAX> p;
int d[NMAX],fact[NMAX];

inline void ciur()
{
	int i,j;
	for(i=2;i<=NMAX-1;i++)
		if(p[i]==0) {
			for(j=i+i;j<=NMAX-1;j=j+i)
				p[j]=1;
			fact[++fact[0]]=i;
		}
}

inline long long pinex(long long a, long long b)
{
	long long sol,i,j,prod;
	int k,nr;
	if(b==1)
		return a;
	i=1;
	k=0;
	while(b>1 && i<=fact[0]) {
		if(b%fact[i]==0) {
			d[++k]=fact[i];
			while(b%fact[i]==0)
				b=b/fact[i];
		}
		i++;
	}
	if(b>1)
		d[++k]=b;
	sol=0;
	for(i=1;i<=(1<<k)-1;i++) {
		nr=0;
		prod=1;
		for(j=0;j<=k-1;j++)
			if(i&(1<<j)) {
				nr++;
				prod=1LL*prod*d[j+1];
			}
		if(nr%2)
			nr=1;
		else nr=-1;
		sol=0LL+sol+1LL*nr*a/prod;
	}
	return 0LL+a-sol;
}

int main ()
{
	long long n,p,q,mij,x,nr,sol;
	ifstream f("frac.in");
	ofstream g("frac.out");
	f>>n>>x;
	p=1;
	q=20;
	ciur();
	while(p<=q) {
		mij=0LL+p+1LL*(0LL+q-p)/2;
		nr=pinex(mij,n);
		if(nr==x)
			sol=mij;
		if(nr<x)
			p=1LL+mij;
		else q=mij-1LL;
	}
	g<<sol;
	g.close();
	return 0;
}