You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

【题目描述】

小明最近在研究时光机器，但是要完成这项工作的话，他需要一个具有特定值的电阻。

但是，小明只有许多电阻值R0=1的电阻，可以由这些电阻器构造其他电阻的元件。我们称下面这些都叫元件：

（1） 一个电阻。

（2） 一个元件e和一个电阻串联。

（3） 一个元件e和一个电阻并联。

如果是一个元件e和一个电阻串联，那么新的元件的电阻R=Re+R0。

如果是一个元件e和一个电阻并联，那么新的元件的电阻R=1/(1/Re+1/R0)=1/(1/Re+1)。

Re代表用来连接的那个元件。

小明需要组装一个电阻为分数的元件，请问制造这种元件最少需要多少个电阻？

【输入格式】

输入包含两个整数a和b（1<=a,b<=10^18）代表分子和分母,保证分数是不可约的，数据保证一定有解。

【输出格式】

输出一个整数，代表问题的解。

【样例输入1】

1 1

【样例输出1】

1

【样例输入2】

3 2

【样例输出2】

3

【样例输出3】

199 200

【样例输出3】

200

【说明】

样例1中显然只需要一个电阻即可。

样例2中，构造方式如下图：可以并联2个电阻形成一个元件再串联一个电阻即可。