题目描述

Bartosz 在庆祝他的生日时收到了一个尺寸为 $N \times M$ 的矩形蛋糕。由于他只喜欢方形的蛋糕块，他决定按照一种特殊的方法把整个蛋糕切成正方形。

每次切蛋糕时，Bartosz 都会将当前蛋糕中能切出的最大正方形切下来，并且这个正方形必须至少有三条边贴着当前剩余矩形的边。这个过程不断重复，直到蛋糕被完全切成若干个正方形。

例如，假设矩形的尺寸为 $5 \times 4$，如下图所示：

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

在这个例子中，他会先切下一个 $4 \times 4$ 的正方形。剩下的蛋糕为 $1 \times 4$ 的矩形。然后，他会切出 $1 \times 1$ 的正方形共四次。

给定初始蛋糕的尺寸 $N \times M$，请你计算使用这种切法总共可以得到多少个正方形。

实现细节

你需要实现如下函数：

int32 count_square_cakes(int32 N, int32 M)

• $N$：蛋糕的宽度；
• $M$：蛋糕的高度；
• 该函数需要返回需要切出的正方形个数；
• 注意，这个函数每次运行会被调用 $T$ 次。

输入格式

输入格式如下：

第一行，一个整数 $T$，表示测试用例数量。
接下来 $T$ 行，每行含两个整数 $N, M$，表示蛋糕的宽度和高度。
评测器会对每组数据调用一次 count_square_cakes(N, M) 并输出结果。

输出格式

对每组数据输出一行，表示将蛋糕全部切成正方形所需的总块数。

提示

样例说明

对于调用 count_square_cakes(5, 4)，上述已经解释，答案为 $5$。

对于调用 count_square_cakes(6, 6)，原矩形已经是正方形，答案为 $1$。

对于调用 count_square_cakes(11, 2)，矩形变化为：$11 \times 2$，$9 \times 2$，$7 \times 2$，$5 \times 2$，$3 \times 2$，$1 \times 2$，$1 \times 1$。因此将得到五个 $2 \times 2$ 正方形和两个 $1 \times 1$ 正方形，共 $7$ 块。

对于调用 count_square_cakes(12, 6)，矩形会被切成两个 $6 \times 6$ 的正方形。

对于调用 count_square_cakes(18, 5)，过程为：$18 \times 5$，$13 \times 5$，$8 \times 5$，$3 \times 5$，$3 \times 2$，$1 \times 2$，$1 \times 1$。所以得到三个 $5 \times 5$ 正方形，两个 $2 \times 2$ 正方形，两个 $1 \times 1$ 正方形，总共 $7$ 块。

数据范围与约定

• $1 \le T \le 2\times 10^5$；
• $1 \le M \le N \le 10^9$。

提示

1. 子任务 1（6 分）：$M = 1$；
2. 子任务 2（11 分）：$N \le 3$；
3. 子任务 3（21 分）：$N \le 5000$，$T \le 100$；
4. 子任务 4（17 分）：$N \le 5000$；
5. 子任务 5（27 分）：$N \le 10^5$，$T \le 100$；
6. 子任务 6（18 分）：无额外限制。

由 ChatGPT 5 翻译