← 返回题目列表

Codeforces · 527/A

A. 玩纸

中文机器翻译题面 查看原题

有一天,Vasya 坐在一堂不太有趣的数学课上,用一张 a mm × b mm 的矩形纸 (a > b) 折纸。通常制作折纸的第一步是将矩形纸沿直角平分线折叠,然后剪掉多余的部分,制成一张正方形纸。

用正方形纸制作了一艘纸船后,瓦西亚查看了剩余的 (a - b) mm × b mm 纸条。他想到以同样的方式使用这张纸条来制作折纸,然后使用剩余的部分(如果存在)等等。当他剩下一张正方形纸的那一刻,他将用它制作最后一艘船并停下来。

你能确定 Vasya 在课程中将制造多少艘船吗?

输入

输入的第一行包含两个整数 a、b (1 ≤ b < a ≤ 1012) — 原始纸张的尺寸。

输出

打印一个整数——Vasya 将制造的船只数量。

示例

输入 #1

2 1

输出 #1

2

输入 #2

10 7

输出 #2

6

输入 #3

1000000000000 1

输出 #3

1000000000000

注意

第一个和第二个样本测试的图片。