P13392 [GCJ 2010 #1A] Number Game

Arya 和 Bran 正在玩一个游戏。最初，黑板上写着两个正整数 $A$ 和 $B$。两位玩家轮流行动，Arya 先手。在每一回合，玩家可以将 $A$ 替换为 $A - k \times B$（$k$ 为任意正整数），或者将 $B$ 替换为 $B - k \times A$（$k$ 为任意正整数）。第一个使得其中一个数变为零或负数的人输掉游戏。 例如，如果初始数字为 $(12, 51)$，游戏过程可能如下： - Arya 将 $51$ 替换为 $51 - 3 \times 12 = 15$，黑板上变为 $(12, 15)$。 - Bran 将 $15$ 替换为 $15 - 1 \times 12 = 3$，黑板上变为 $(12, 3)$。 - Arya 将 $12$ 替换为 $12 - 3 \times 3 = 3$，黑板上变为 $(3, 3)$。 - Bran 将其中一个 $3$ 替换为 $3 - 1 \times 3 = 0$，Bran 输掉游戏。 我们称 $(A, B)$ 为“必胜态”，如果 Arya 无论 Bran 如何应对，都能保证获胜。 给定四个整数 $A_1$、$A_2$、$B_1$、$B_2$，请统计有多少个 $(A, B)$ 是必胜态，且满足 $A_1 \leq A \leq A_2$ 且 $B_1 \leq B \leq B_2$。

输入的第一行包含一个整数 $T$，表示测试用例的数量。接下来 $T$ 行，每行包含四个整数 $A_1$、$A_2$、$B_1$、$B_2$，用空格分隔。

对于每个测试用例，输出一行，格式为 "Case #x: y"，其中 $x$ 表示测试用例编号（从 1 开始），$y$ 表示满足条件的必胜态 $(A, B)$ 的数量。

**数据范围** - $1 \leqslant T \leqslant 100$。 - $1 \leqslant A_1 \leqslant A_2 \leqslant 1,000,000$。 - $1 \leqslant B_1 \leqslant B_2 \leqslant 1,000,000$。 **小数据（16 分，测试点 1 - 可见）** - 时间限制：3 秒。 - $A_2 - A_1 \leqslant 30$。 - $B_2 - B_1 \leqslant 30$。 **大数据（25 分，测试点 2 - 隐藏）** - 时间限制：9 秒。 - $A_2 - A_1 \leqslant 999,999$。 - $B_2 - B_1 \leqslant 999,999$。 - 无其他限制。 由 ChatGPT 4.1 翻译