Arya 和 Bran 正在玩一个游戏。黑板上最初写着两个正整数 $A$ 和 $B$。玩家轮流进行操作，Arya 先手。在每一轮中，玩家可以将 $A$ 替换为 $A - k \cdot B$（其中 $k$ 为任意正整数），或者将 $B$ 替换为 $B - k \cdot A$（其中 $k$ 为任意正整数）。第一个使其中一个数字变为小于或等于 $0$ 的玩家输掉比赛。

例如，如果初始数字为 $(12, 51)$，游戏过程可能如下：

• Arya 将 $51$ 替换为 $51 - 3 \cdot 12 = 15$，黑板上剩下 $(12, 15)$。
• Bran 将 $15$ 替换为 $15 - 1 \cdot 12 = 3$，黑板上剩下 $(12, 3)$。
• Arya 将 $12$ 替换为 $12 - 3 \cdot 3 = 3$，黑板上剩下 $(3, 3)$。
• Bran 将其中一个 $3$ 替换为 $3 - 1 \cdot 3 = 0$，从而输掉比赛。

如果无论 Bran 如何操作，Arya 都能在以 $(A, B)$ 为初始状态的游戏中获胜，我们就称 $(A, B)$ 为一个必胜位置。

给定四个整数 $A_1, A_2, B_1, B_2$，计算有多少个满足 $A_1 \le A \le A_2$ 且 $B_1 \le B \le B_2$ 的必胜位置 $(A, B)$。

输入格式

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

输出格式

对于每个测试用例，输出一行 "Case #x: y"，其中 $x$ 是用例编号（从 1 开始），$y$ 是满足 $A_1 \le A \le A_2$ 且 $B_1 \le B \le B_2$ 的必胜位置 $(A, B)$ 的数量。

数据范围

$1 \le T \le 100$。 $1 \le A_1 \le A_2 \le 1,000,000$。 $1 \le B_1 \le B_2 \le 1,000,000$。

样例

样例输入 1

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

样例输出 1

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