Problem D
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.

Input

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

Output

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