P14039 [PAIO 2025] Cake

Bartosz 在庆祝他的生日时收到了一个尺寸为 $N \times M$ 的矩形蛋糕。由于他只喜欢方形的蛋糕块，他决定按照一种特殊的方法把整个蛋糕切成正方形。 每次切蛋糕时，Bartosz 都会将当前蛋糕中能切出的最大正方形切下来，并且这个正方形必须至少有三条边贴着当前剩余矩形的边。这个过程不断重复，直到蛋糕被完全切成若干个正方形。 例如，假设矩形的尺寸为 $5 \times 4$，如下图所示： ::::align{center}  :::: 在这个例子中，他会先切下一个 $4 \times 4$ 的正方形。剩下的蛋糕为 $1 \times 4$ 的矩形。然后，他会切出 $1 \times 1$ 的正方形共四次。 给定初始蛋糕的尺寸 $N \times M$，请你计算使用这种切法总共可以得到多少个正方形。 ### 实现细节 你需要实现如下函数： ```cpp 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 200000$ * $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 100000$，$T \le 100$ 6. 子任务6（18分）：无额外限制 由 ChatGPT 5 翻译