Vasya is studying number theory. He has denoted a function f(a, b) such that:

  * f(a, 0) = 0; 
  * f(a, b) = 1 + f(a, b - gcd(a, b)), where gcd(a, b) is the greatest common divisor of a and b. 



Vasya has two numbers x and y, and he wants to calculate f(x, y). He tried to do it by himself, but found out that calculating this function the way he wants to do that might take very long time. So he decided to ask you to implement a program that will calculate this function swiftly.

Input

The first line contains two integer numbers x and y (1 ≤ x, y ≤ 1012).

Output

Print f(x, y).

Examples

Input

3 5


Output

3


Input

6 3


Output

1
import java.util.*;
import java.io.*;
//import java.text.*;

public class Main{
//    final long MOD = (long)1e9+7, IINF = (long)1e19;
//    final int MAX = (int)1e5+1, MX = (int)1e7+1, INF = (int)1e9;
//    DecimalFormat df = new DecimalFormat("0.00000000");
//    final double EPS = 1e-8;
    FastReader in;
    PrintWriter out;
    boolean multipleTC = false;
    
    public static void main(String[] args) throws Exception{new Main().run();};
    void run(){
        in = new FastReader();
        out = new PrintWriter(System.out);
        for(int i = 1, t = (multipleTC)?ni():1; i<=t; i++)solve(i);
        out.flush();
        out.close();
    }
    
    void solve(int TC){
        pn(f(nl(), nl()));
    }
    
    long f(long a,long b){
        if(b==0)return 0;
        if(a==1)return b;
        long g = gcd(a,b);
        a/=g;
        b/=g;
        long m = b, c = a;
        for(long i = 2; i*i<=a; i++){
            if(c%i==0)m = Math.min(m, b%i);
            while(c%i==0)c/=i;
        }
        if(c!=1)m = Math.min(b%c, m);
        return m+f(a,b-m);
    }
    
    
    int[] sort(int[] a){
        if(a.length==1)return a;
        int mid = a.length/2;
        int[] b = sort(Arrays.copyOfRange(a,0,mid)), c = sort(Arrays.copyOfRange(a,mid,a.length));
        for(int i = 0, j = 0, k = 0; i< a.length; i++){
            if(j<b.length && k<c.length){
                if(b[j]<c[k])a[i] = b[j++];
                else a[i] = c[k++];
            }else if(j<b.length)a[i] = b[j++];
            else a[i] = c[k++];
        }
        return a;
    }
    
    long[] sort(long[] a){
        if(a.length==1)return a;
        int mid = a.length/2;
        long[] b = sort(Arrays.copyOfRange(a,0,mid)), c = sort(Arrays.copyOfRange(a,mid,a.length));
        for(int i = 0, j = 0, k = 0; i< a.length; i++){
            if(j<b.length && k<c.length){
                if(b[j]<c[k])a[i] = b[j++];
                else a[i] = c[k++];
            }else if(j<b.length)a[i] = b[j++];
            else a[i] = c[k++];
        }
        return a;
    }
    
    

    int[] ia(int n){
        int[] out = new int[n];
        for(int i = 0; i< n; i++)out[i] = ni();
        return out;
    }

    long[] la(int n){
        long[] out = new long[n];
        for(int i = 0; i< n; i++)out[i] = nl();
        return out;
    }

    long gcd(long a, long b){return (b==0)?a:gcd(b,a%b);}
    int gcd(int a, int b){return (b==0)?a:gcd(b,a%b);}
    int bitcount(long n){return (n==0)?0:(1+bitcount(n&(n-1)));}
    void p(Object o){out.print(o);}
    void pn(Object o){out.println(o);}
    void pni(Object o){out.println(o);out.flush();}
    String n(){return in.next();}
    String nln(){return in.nextLine();}
    int ni(){return Integer.parseInt(in.next());}
    long nl(){return Long.parseLong(in.next());}
    double nd(){return Double.parseDouble(in.next());}

    class FastReader{
        BufferedReader br;
        StringTokenizer st;
        public FastReader(){
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        public FastReader(String s) throws Exception{
            br = new BufferedReader(new FileReader(s));
        }

        String next(){
            while (st == null || !st.hasMoreElements()){
                try{
                    st = new StringTokenizer(br.readLine());
                }catch (IOException  e){
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        String nextLine(){
            String str = "";
            try{
                str = br.readLine();
            }catch (IOException e){
                e.printStackTrace();
            }
            return str;
        }
    }
}