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

每次 Bartosz 切蛋糕时，他都会切出尽可能大的正方形，使得该正方形的至少三条边与当前剩余矩形蛋糕的边重合。这个过程不断重复，直到整块蛋糕被完全分割成正方形。

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

在这个例子中，他将切出一个 $4 \times 4$ 的正方形。之后，他会得到一个 $1 \times 4$ 的矩形。因此，他接下来会切出四个 $1 \times 1$ 的正方形。

给定初始蛋糕的尺寸 $N \times M$，求出 Bartosz 使用这种切割方法最终能获得的正方形总数。

实现细节

你需要实现以下函数：

int32 count_square_cakes(int32 N, int32 M)

• N：蛋糕的宽度
• M：蛋糕的高度
• 该函数应返回获得的正方形数量
• 请注意，在每次运行中，该函数将被调用 $T$ 次。

数据范围

• $1 \le T \le 200\,000$
• $1 \le M \le N \le 10^9$

子任务

• 子任务 1（6 分）：$M = 1$
• 子任务 2（11 分）：$N \le 3$
• 子任务 3（21 分）：$N \le 5\,000$；$T \le 100$
• 子任务 4（17 分）：$N \le 5\,000$
• 子任务 5（27 分）：$N \le 100\,000$；$T \le 100$
• 子任务 6（18 分）：无附加限制

样例

考虑以下函数调用：

• 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$。因此，将会有 5 个 $2 \times 2$ 的正方形和 2 个 $1 \times 1$ 的正方形，总共 7 个。
• count_square_cakes(12, 6)：矩形将被切成 2 个 $6 \times 6$ 的正方形，答案为 2。
• count_square_cakes(18, 5)：矩形的尺寸变化如下：$18 \times 5$，$13 \times 5$，$7 \times 5$，$2 \times 5$，$2 \times 3$，$2 \times 1$，$1 \times 1$。因此，将会有 3 个 $5 \times 5$ 的正方形、2 个 $2 \times 2$ 的正方形和 2 个 $1 \times 1$ 的正方形，总共 7 个。

评测程序示例

样例评测程序将按以下格式读取输入：

• 第 1 行：一个整数 $T$
• 接下来的 $T$ 行：每行包含两个整数 $N, M$，表示蛋糕的宽度和高度。评测程序将对每一行调用 count_square_cakes(N, M) 函数并输出结果。