Playing with Paper

题意翻译

有一天，Vasya坐在教室里上数学课，课上老师在讲一个关于折纸的问题。有一张$a$ 毫米$\times b$ 毫米的纸$(a>b)$ ，每次按照下图所示，折出一个边长为$b$ 的等腰直角三角形，然后把直角三角形减掉，然后对于余下$b\times (a-b)$ 的矩形做同样的处理，一直重复这个过程，直到最后这张纸被剪没了。  现在的问题是，对于一张$a\times b(a>b)$ 的纸，需要折多少次才能使得这张纸被剪没了。 ### 输入数据 输入只有一行两个正整数$a$ 和$b(1\leq b<a\leq10^{12})$ ，表示矩形的大小。 ### 输出数据 输出需要折的次数。 ### 提示 第一个和第二个样例  感谢@馒头精 提供的翻译

题目描述

One day Vasya was sitting on a not so interesting Maths lesson and making an origami from a rectangular $ a $ mm $ × $ $ b $ mm sheet of paper ( $ a>b $ ). Usually the first step in making an origami is making a square piece of paper from the rectangular sheet by folding the sheet along the bisector of the right angle, and cutting the excess part. After making a paper ship from the square piece, Vasya looked on the remaining $ (a-b) $ mm $ × $ $ b $ mm strip of paper. He got the idea to use this strip of paper in the same way to make an origami, and then use the remainder (if it exists) and so on. At the moment when he is left with a square piece of paper, he will make the last ship from it and stop. Can you determine how many ships Vasya will make during the lesson?

输入输出格式

输入格式

The first line of the input contains two integers $ a $ , $ b $ ( $ 1<=b<a<=10^{12} $ ) — the sizes of the original sheet of paper.

输出格式

Print a single integer — the number of ships that Vasya will make.

输入输出样例

输入样例 #1

2 1

输出样例 #1

2

输入样例 #2

10 7

输出样例 #2

6

输入样例 #3

1000000000000 1

输出样例 #3

1000000000000

说明

Pictures to the first and second sample test.