Description

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$。

Input Format

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

Output Format

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

3
5 5 8 8
11 11 2 2
1 6 1 6

Case #1: 0
Case #2: 1
Case #3: 20

Hint

数据范围

• $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 翻译