在我们的星球 Jamcode IX 上，曾发生过三次“伟大事件”。它们分别发生在 26000、11000 和 6000 个 slarboseconds（时间单位）之前。在 4000 个 slarboseconds 之后，距离所有这些事件发生的时间都将是 5000 个 slarboseconds 的倍数，且这是可能的最大公约数……于是末日降临了。

幸运的是，你生活在 Jamcode X 上！Jamcode IX 的末日发生在不到一年前。但 Jamcode X 有一个令人担忧的预言：“在清算时刻之后，在 $N$ 个伟大事件的第一个最佳周年纪念日，末日将会降临。64 位整数救不了你。你已被警告。”

Jamcode X 的人们对这个预言感到非常担忧。所有的伟大事件都已经发生，并且它们的时间已经精确到最近的 slarbosecond；但没有人知道它们的最佳周年纪念日何时到来。在研究了一位来自 Jamcode IX 的科学家的日记后，研究该问题的科学家们提出了一个理论：

清算时刻就是现在，即你解决这个问题的那一刻。在从现在起 $y \ge 0$ 个 slarboseconds 后的某个时间，距离每个伟大事件发生的时间都将能被某个最大数 $T$ 整除。如果你能找到使这个最大可能的 $T$ 成立的最小 $y$ 值，那将给出末日降临的最佳周年纪念日。

例如，在 Jamcode IX 上，有 3 个伟大事件，它们分别发生在清算时刻之前的 26000、11000 和 6000 个 slarboseconds。4000 个 slarboseconds 后，距离每个事件的时间都是 $T=5000$ 个 slarboseconds 的倍数，于是末日降临了。

你的任务是计算距离末日降临的时间。但请记住那个预言：尽管 Jamcode X 的人们已经解决了两年的问题，并且 64 位整数一直都足够使用，但它们现在或将来可能不再足够了。

输入格式

输入的第一行包含测试用例的数量 $C$。接下来是 $C$ 行。每行以一个整数 $N$ 开头，后跟一个空格，然后是 $N$ 个以空格分隔的整数 $t_i$，表示距离伟大事件 $i$ 发生的时间（单位为 slarboseconds）。

输出格式

对于每个测试用例，输出一行 "Case #x: y"，其中 $x$ 是用例编号（从 1 开始），$y$ 是使 $t_i + y$ 对于所有 $i$ 都能被最大可能的整数因子 $T$ 整除的最小时间（单位为 slarboseconds）。

数据范围

$1 \le C \le 100$。 $t_i \neq t_j$（对于某些 $i, j$）。

小数据（测试集 1 - 可见；10 分）

$2 \le N \le 3$。 $1 \le t_i \le 10^8$。

大数据（测试集 2 - 隐藏；23 分）

$2 \le N \le 1000$。 $1 \le t_i \le 10^{50}$。

样例

样例输入 1

3
3 26000000 11000000 6000000
3 1 10 11
2 800000000000000000001 900000000000000000001

样例输出 1

Case #1: 4000000
Case #2: 0
Case #3: 99999999999999999999

说明

幸运的是，对于 Jamcode 系统的居民来说，“末日”被证明是“盛大派对”的误译。Jamcode IX 的人没人费心去传达这一点，因为他们玩得太开心了。