Minimal Square Partition

Given a rectangle with integer side lengths a and b, your task is to cut it into the smallest possible number of squares with integer side lengths.

The optimal strategy is based on the following observation: if a and b are the side lengths of the rectangle (assume without loss of generality that a ≥ b), then you can cut out \(\lfloor a/b \rfloor\) squares of size \(b \times b\) from the rectangle. You are then left with a smaller rectangle of dimensions \((a \bmod b) \times b\). Recursively apply this process until the rectangle becomes a square. When the rectangle is a square (a = b), only one square is needed.

The recursion can be formally written as:

\[ f(a,b) = \begin{cases} 1, & \text{if } a = b, \\ \lfloor a/b \rfloor + f(b, a \bmod b), & \text{if } a > b. \end{cases} \]

inputFormat

The input consists of a single line containing two positive integers a and b separated by a space, representing the side lengths of the rectangle.

outputFormat

Output a single integer representing the smallest number of squares that the rectangle can be cut into.

sample

2 3

3