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.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.io.FilterInputStream;
import java.io.BufferedInputStream;
import java.util.ArrayList;
import java.io.InputStream;

/**
 * @author khokharnikunj8
 */

public class Main {
    public static void main(String[] args) {
        new Thread(null, new Runnable() {
            public void run() {
                new Main().solve();
            }
        }, "1", 1 << 26).start();
    }

    void solve() {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        ScanReader in = new ScanReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        EVasyasFunction solver = new EVasyasFunction();
        solver.solve(1, in, out);
        out.close();
    }

    static class EVasyasFunction {
        ArrayList<Long> arrayList;

        public void findIt(long n) {
            arrayList = new ArrayList<>();
            if (n % 2 == 0) {
                arrayList.add(2l);
                while (n % 2 == 0) n /= 2;
            }
            for (long i = 3; i * i <= n; i += 2) {
                if (n % i == 0) {
                    arrayList.add(i);
                    while (n % i == 0) n /= i;

                }
            }
            if (n > 2)
                arrayList.add(n);
        }

        public long LOL(long a, long b) {
            if (b == 0) return 0;
            long gcd = CodeHash.gcd(a, b);
            findIt(a / gcd);
            long low = 0;
            for (long i : arrayList) {
                if (i < (10e18) / gcd) {
                    long tt = (b / (i * gcd)) * (i * gcd);
                    low = Math.max(low, tt);
                }
            }
            return LOL(a, low) + (b - low) / gcd;
        }

        public void solve(int testNumber, ScanReader in, PrintWriter out) {
            arrayList = new ArrayList<>();
            long a = in.scanLong();
            long b = in.scanLong();
            out.println(LOL(a, b));

        }

    }

    static class ScanReader {
        private byte[] buf = new byte[4 * 1024];
        private int index;
        private BufferedInputStream in;
        private int total;

        public ScanReader(InputStream inputStream) {
            in = new BufferedInputStream(inputStream);
        }

        private int scan() {
            if (index >= total) {
                index = 0;
                try {
                    total = in.read(buf);
                } catch (Exception e) {
                    e.printStackTrace();
                }
                if (total <= 0) return -1;
            }
            return buf[index++];
        }

        private boolean isWhiteSpace(int n) {
            if (n == ' ' || n == '\n' || n == '\r' || n == '\t' || n == -1) return true;
            else return false;
        }

        public long scanLong() {
            long integer = 0;
            int n = scan();
            while (isWhiteSpace(n)) n = scan();
            int neg = 1;
            if (n == '-') {
                neg = -1;
                n = scan();
            }
            while (!isWhiteSpace(n)) {
                if (n >= '0' && n <= '9') {
                    integer *= 10;
                    integer += n - '0';
                    n = scan();
                }
            }
            return neg * integer;
        }

    }

    static class CodeHash {
        public static long gcd(long a, long b) {
            if (b == 0)
                return a;
            else
                return gcd(b, a % b);
        }

    }
}

