Bob 学会了一个需要非常特殊准备的魔术。一旦他掌握了这个魔术，他就能为世界带来和平，但如果他失败了，世界就会毁灭。

准备工作如下：有两个容器，最初一个为空，另一个有 $X$ 个弹珠。Bob 有一台弹珠克隆机，它会克隆弹珠数量较多的那个容器里的弹珠，然后将新克隆出的弹珠倒入另一个容器中（例如，如果两个容器分别有 7 个和 4 个弹珠，克隆步骤后它们将分别有 7 个和 11 个弹珠）。机器执行此克隆操作恰好 $M$ 次。然而，机器中存在一个故障，在执行了 $N$ 次克隆操作（$N \le M$）后，它会向弹珠数量较多的那个容器中额外添加 $Y$ 个弹珠。然后机器将继续正常执行剩余的 $M - N$ 次克隆操作。

在克隆操作过程中，如果两个容器中的弹珠数量相同，则可以将其中任何一个视为弹珠数量较多的容器。

现在，Bob 机器中的故障威胁着要毁灭世界。但他书呆子气的朋友 Alice 告诉他，她知道如何修复它。他所要做的就是计算出克隆机工作完成后两个容器中弹珠数量的最大公约数。你能帮 Bob 拯救世界吗？

输入格式

你的程序将在一个或多个测试用例上进行测试。输入的第一行是一个整数 $T$ ($1 \le T \le 1,000$)，表示测试用例的数量。接下来是 $T$ 个测试用例。每个测试用例由一行组成，包含 4 个由空格分隔的整数 $X, N, Y$ 和 $M$ ($1 \le X, Y \le 1,000$) ($0 \le N \le 70$) ($N \le M \le 100,000$)，这些数字的含义如上所述。

输出格式

对于每个测试用例，打印一行包含 “Case n:”（不含引号，其中 n 是测试用例编号，从 1 开始），后跟一个空格，再后跟机器工作完成后两个容器中弹珠数量的最大公约数。

样例

输入 1

2
4 3 6 5
5 1 15 2

输出 1

Case 1: 2
Case 2: 5

说明

在第一个样例测试用例中，每一步之后每个容器中的弹珠数量如下：$(4, 0), (4, 4), (4, 8), (12, 8), (18, 8), (18, 26), (44, 26)$。44 和 26 的最大公约数是 2。