题目背景

Fortunately for the peoples of the Jamcode system, "the apocalypse" turned out to be a mistranslation of "the giant party." Nobody from Jamcode IX bothered to pass this along, because they were having so much fun.

题目描述

On our planet, Jamcode IX, three Great Events occurred. They happened $26000$, $11000$ and $6000$ slarboseconds ago. In $4000$ slarboseconds, the amount of time since all of those events will be multiples of $5000$ slarboseconds, the largest possible amount... and the apocalypse will come.

Luckily for you, you live on Jamcode X! The apocalypse came on Jamcode IX less than a year ago. But Jamcode X has a worrying prophecy: "After the moment of reckoning, on the first optimum anniversary of the N Great Events, the apocalypse will come. 64 bits will not save you. You have been warned."

The people of Jamcode X are very concerned by this prophecy. All of the Great Events have already happened, and their times have been measured to the nearest slarbosecond; but nobody knows when their optimum anniversary will occur. After studying the diary of a scientist from Jamcode IX, scientists working on the problem have come up with a theory:

The moment of reckoning is now, the moment you solve this problem. At some time $y \geqslant 0$ slarboseconds from now, the number of slarboseconds since each of the Great Events will be divisible by some maximum number $T$. If you can find the smallest value of $y$ that gives this largest possible $T$, that will give you the optimum anniversary when the apocalypse will come.

On Jamcode IX, for example, there were 3 Great Events and they happened $26000$, $11000$ and $6000$ slarboseconds before the moment of reckoning. $4000$ slarboseconds later, the amount of time since each event was a multiple of $T=5000$ slarboseconds, and the apocalypse came.

Your job is to compute the amount of time until the apocalypse comes. But remember the prophecy: even though the people of Jamcode X have been solving problems for two years, and 64-bit integers have always been enough, they might not always be enough now or in the future.

输入格式

The first line of the input gives the number of test cases, $C$. $C$ lines follow. Each starts with a single integer $N$, which is followed by a space and then $N$ space-separated integers $t_i$, the number of slarboseconds since Great Event i occurred.

输出格式

For each test case, output one line containing "Case #x: y", where $x$ is the case number (starting from 1) and $y$ is the minimum number of slarboseconds until $t_i + y$ is a multiple of the largest possible integer factor $T$ for all $i$.

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

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

提示

Limits

• $1 \leqslant C \leqslant 100.$
• $t_{i} \neq t_{j}$ for some $i, j$.

Small dataset (10 Pts, Test set 1 - Visible)

• $2 \leqslant N \leqslant 3.$
• $1 \leqslant t_{i} \leqslant 10^{8}.$

Large dataset (23 Pts, Test set 2 - Hidden)

• $2 \leqslant N \leqslant 1000.$
• $1 \leqslant t_{i} \leqslant 10^{50}.$