Rectangle

Time limit1sMemory limit128 MB

Summary

Repeatedly cut the largest possible square from an n by m rectangle and count how many squares result.

Level: Easy3 of 10
Topics: Math, Implementation, Simulation
Solved: No attempts yet

Problem

Vilibald has decided to cut a rectangular grid page of size $n \times m$ cells into squares. First, with a single straight cut, he cuts off the largest possible square. He then removes that square and repeats the process on the remaining rectangle. Continuing in this way -- always cutting off the largest possible square -- Vilibald keeps cutting until the remaining piece is itself a square.

Given the two integers $n$ and $m$ , write a program that computes how many squares Vilibald obtains by cutting the rectangle in the manner described above.

Input

The first line contains two positive integers $n$ and $m$ , separated by a space ( $n < 10000$ , $m < 10000$ ).

Output

Print, on a single line, the number of squares Vilibald obtains.

Examples2

Example 1
Input
```
3 7
```
Expected output
```
5
```
Example 2
Input
```
9999 9999
```
Expected output
```
1
```