题目描述

Bartosz is celebrating his birthday and receives a rectangular cake with dimensions $N \times M$. 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 $5 \times 4$, as shown in the picture below.

::::align{center} ::::

In such example, he will slice out the square $4 \times 4$. After that, he will get a rectangle $1 \times 4$. Therefore, he will slice out a square $1 \times 1$ then for four times.

Given the initial cake dimensions $N \times M$, 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)

• $N$: the width of the cake
• $M$: the height of the cake
• The function should return the number of squares obtained
• Note that this function will be called $T$ 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: $11 \times 2$, $9 \times 2$, $7 \times 2$, $5 \times 2$, $3 \times 2$, $1 \times 2$, $1 \times 1$. Therefore, there will be five $2 \times 2$ squares and two $1 \times 1$ squares. 7 in total.

Consider the following call count_square_cakes(12, 6). The rectangle will be cut into two $6 \times 6$ squares.

Consider the following call count_square_cakes(18, 5). The sizes of the rectangle will be as follows: $18 \times 5$, $13 \times 5$, $8 \times 5$, $3 \times 5$, $3 \times 2$, $1 \times 2$, $1 \times 1$. Therefore, there will be three $5 \times 5$ squares, two $2 \times 2$ squares, and two $1 \times 1$ squares. 7 in total.

Sample Grader

The sample grader reads the input in the following format:

• Line 1: One integer $T$
• Next $T$ lines: two integers $N, M$ 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.

Constraints

• $1 \le T \le 200000$.
• $1 \le M \le N \le 10^9$.

Scoring

1. Subtask 1 (6 points): $M = 1$
2. Subtask 2 (11 points): $N \le 3$
3. Subtask 3 (21 points): $N \le 5000$; $T \le 100$
4. Subtask 4 (17 points): $N \le 5000$
5. Subtask 5 (27 points): $N \le 100000$; $T \le 100$
6. Subtask 6 (18 points): No additional constraints