5275: 折纸

内存限制:256 MB 时间限制:1 S
题面:传统 评测方式:文本比较 上传者:
提交:6 通过:4

题目描述



有一天,Vasya坐在教室里上数学课,课上老师在讲一个关于折纸的问题。有一张a 毫米×b 毫米的纸(a>b) ,每次按照下图所示,折出一个边长为b 的等腰直角三角形,然后把直角三角形减掉,然后对于余下b×(ab) 的矩形做同样的处理,一直重复这个过程,直到最后这张纸被剪没了。


现在的问题是,对于一张 a×b(a>b) 的纸,需要折多少次才能使得这张纸被剪没了。

输入格式

输入的第一行包含两个整数a、b (1≤b<a≤1012),即原始纸张的大小。

输出格式

输出需要折的次数。



Examples
Input
2 1
Output
2
Input
10 7
Output
6
Input
1000000000000 1
Output
1000000000000
Note
Pictures to the first and second sample test.


输入样例 复制

2 1

输出样例 复制

2

数据范围与提示

第一、二个测试样例的示意图