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
/*
 * Author Ayub Subhaniya
 * Institute DA-IICT
 */

import java.io.*;
import java.math.*;
import java.util.*;


public class Codeforces408 {
	
	InputStream in;
	PrintWriter out;
	
	void solve() 
	{
		long x=nl();
		long y=nl();
		long g=gcd(x,y);
		long k=y/g;
		long steps=0;
		HashSet<Long> primeF=new HashSet<Long>();
		long a=x;
		long idx=2;
		long sqrt=(long)1e6+7;
		while (a!=1)
		{
			if (a%idx==0)
			{
				primeF.add(idx);
				while (a%idx==0)
					a/=idx;
			}
			idx++;
			if (idx>=a||idx>=sqrt)
			{
				primeF.add(a);
				break;
			}
		}
		k--;
		steps++;
		while (k>=1)
		{
			a=x/g;
			HashSet<Long> tmp=new HashSet<>();
			for (long p:primeF)
				if (a%p!=0)
					tmp.add(p);
			for (long p : tmp)
				primeF.remove(p);
			
			long max=0;
			for (long p:primeF)
			{
				long result=k/p;
				result*=p;
				max=Math.max(max, result);
			}
			
			long tmpg=gcd(a,max);
			steps+=k-max;
			g*=tmpg;
			k=max/tmpg;
			if (k<1)
				break;
			k--;
			steps++;
		}
		out.println(steps);
	}
	
	long gcd(long A, long B) {
		if (B == 0)
			return A;
		else
			return gcd(B, A % B);
	}
	

	void run() throws Exception {
		String INPUT = "C:/Users/ayubs/Desktop/input.txt";
		//oj=true;
		in = oj ? System.in : new FileInputStream(INPUT);
		out = new PrintWriter(System.out);
		
			long s = System.currentTimeMillis();
			solve();
			out.flush();
			tr(System.currentTimeMillis() - s + "ms");
		
	}
	public static void main(String[] args) throws Exception {
		new Codeforces408().run();
	}
	
	private byte[] inbuf = new byte[1024];
	public int lenbuf = 0, ptrbuf = 0;
	
	private int readByte() {
		if (lenbuf == -1)
			throw new InputMismatchException();
		if (ptrbuf >= lenbuf) {
			ptrbuf = 0;
			try {
				lenbuf = in.read(inbuf);
			} catch (IOException e) {
				throw new InputMismatchException();
			}
			if (lenbuf <= 0)
				return -1;
		}
		return inbuf[ptrbuf++];
	}
	
	private boolean inSpaceChar(int c) {
		return !(c >= 33 && c <= 126);
	}
	
	private int skip() {
		int b;
		while ((b = readByte()) != -1 && inSpaceChar(b))
			;
		return b;
	}
	
	private double nd() {
		return Double.parseDouble(ns());
	}
	
	private char nc() {
		return (char) skip();
	}
	
	private String ns() {
		int b = skip();
		StringBuilder sb = new StringBuilder();
		while (!(inSpaceChar(b))) { // when nextLine, (inSpaceChar(b) && b != ' ')
			sb.appendCodePoint(b);
			b = readByte();
		}
		return sb.toString();
	}
	
	private char[] ns(int n) {
		char[] buf = new char[n];
		int b = skip(), p = 0;
		while (p < n && !(inSpaceChar(b))) {
			buf[p++] = (char) b;
			b = readByte();
		}
		return n == p ? buf : Arrays.copyOf(buf, p);
	}
	
	private char[][] nm(int n, int m) {
		char[][] map = new char[n][];
		for (int i = 0; i < n; i++)
			map[i] = ns(m);
		return map;
	}
	
	private int[] na(int n) {
		int[] a = new int[n];
		for (int i = 0; i < n; i++)
			a[i] = ni();
		return a;
	}
	
	private int ni() {
		int num = 0, b;
		boolean minus = false;
		while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'))
			;
		if (b == '-') {
			minus = true;
			b = readByte();
		}
		
		while (true) {
			if (b >= '0' && b <= '9') {
				num = num * 10 + (b - '0');
			} else {
				return minus ? -num : num;
			}
			b = readByte();
		}
	}
	
	private long nl() {
		long num = 0;
		int b;
		boolean minus = false;
		while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'))
			;
		if (b == '-') {
			minus = true;
			b = readByte();
		}
		
		while (true) {
			if (b >= '0' && b <= '9') {
				num = num * 10 + (b - '0');
			} else {
				return minus ? -num : num;
			}
			b = readByte();
		}
	}
	
	private boolean oj = System.getProperty("ONLINE_JUDGE") != null;
	
	private void tr(Object... o) {
		if (!oj)
			System.out.println(Arrays.deepToString(o));
	}
}
