Bartosz is celebrating his birthday and receives a rectangular cake with dimensions . As he only likes square-shaped pieces, he decides to cut the entire cake into squares according to a specific method.
Each time Bartosz cuts the cake, he slices out the largest possible square so that at least three sides of the square are flush with the sides of the remaining rectangular piece of the cake. This process repeats until the entire cake is divided into nothing but squares.
For example, let's say that the rectangle has sizes , as shown in the picture below.
::::align{center}
::::
In such example, he will slice out the square . After that, he will get a rectangle . Therefore, he will slice out a square then for four times.
Given the initial cake dimensions , determine the total number of squares Bartosz will obtain using this cutting method.
Implementation Details
You need to implement the following function:
int32 count_square_cakes(int32 N, int32 M)
: the width of the cake
: the height of the cake
The function should return the number of squares obtained
Note that this function will be called times per run
数据范围与提示
Examples
Consider the following call count_square_cakes(5, 4). This was explained above, and the answer is 5.
Consider the following call count_square_cakes(6, 6). Since the original rectangle is already a square, the answer is 1.
Consider the following call count_square_cakes(11, 2). The sizes of the rectangle will be as follows: , , , , , , . Therefore, there will be five squares and two squares. 7 in total.
Consider the following call count_square_cakes(12, 6). The rectangle will be cut into two squares.
Consider the following call count_square_cakes(18, 5). The sizes of the rectangle will be as follows: , , , , , , . Therefore, there will be three squares, two squares, and two squares. 7 in total.
Sample Grader
The sample grader reads the input in the following format:
Line 1: One integer
Next lines: two integers describing the width and height of the cake. The grader will call the method count_square_cakes(N, M) for each of these lines and output the result.
::::