Fair Warning

*On our planet, Jamcode IX, three Great Events occurred.
They happened $26\, 000$,
$11\, 000$ and
$6\, 000$ slarboseconds
ago. In $4\, 000$
slarboseconds, the amount of time since all of those events
will be multiples of $5\,
000$ 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 \geq 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 $26\, 000$, $11\, 000$ and $6\, 000$ slarboseconds before the moment of reckoning. $4\, 000$ slarboseconds later, the amount of time since each event was a multiple of $T=5\, 000$ 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.

You can assume that $1 \leq C \leq 100$, $t_ i \not= t_ j$ for some $i, j$. Furthermore, $2 \leq N \leq 1\, 000$ and $1 \leq t_ i \leq 10^{50}$.

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$.

Sample Input 1 | Sample Output 1 |
---|---|

3 3 26000000 11000000 6000000 3 1 10 11 2 800000000000000000001 900000000000000000001 |
Case #1: 4000000 Case #2: 0 Case #3: 99999999999999999999 |