SP7260 NUMGAME - Number Game

### 题意 Arya和Bran正在玩游戏。最初，两个正整数 **A** 和 **B** 被写在黑板上。 玩家从Arya开始。轮到他或她时，玩家可以 用$A - k\times B$替换 $A$ 来表示任何正整数 $k$，或者用 $B - k \times A$ 替换 $B$ 表示任何正整数 $k$ 。 第一个使数字下降到零或以下的人将输。 例如，如果数字最初是$(12,51)$，则游戏可能如下进行： - Arya用 $51-3 \times 12 = 15$ 代替 $51$，将$(12,15)$留在黑板上。 - Bran用 $15-1\times 12 = 3$ 替换 $15$，将$(12,3)$留在黑板上。 - Arya用 $12-3 \times 3 = 3$ 替换 $12$，将$(3,3)$留在黑板上。 - Bran将$3$替换为$3-1 \times 3 = 0$，然后输了。 如果Arya总是能赢得以黑板$(A,B)$开头的游戏，那么无论Bran做什么，我们都会说$ (A,B)$是 一对`winning position`。 由于四个整数 $A_1$,$A_2$,$B_1$,$B_2$，计算有多少对`winning position` $(A,B)$并且 $ A_1 \le A \le A_2$ & $ B_1 \le B \le B_2$。

输入的第一行给出了测试用例数$T$。 随后是$T$个测试用例，每行一个，包含四个以空格分隔的整数 $A_1$,$A_2$,$B_1$,$B_2$。 $1≤ T ≤250 $。 $1≤ A_1 ≤ A_2≤1,000,000$。 $1 ≤ B_1≤ B_2 ≤ 1,000,000$。 $A_2-A_1≤999,999$。 $B_2-B_1≤999,999$。

For each test case, output one line containing "Case #x: y", where x is the case number (starting from 1), and y is the number of winning positions (**A**, **B**) with **A $ _{1} $** A A $ _{2} $ and **B $ _{1} $** B B $ _{2} $ .