Fair Warning (Large)

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 each of those events will be a multiple of 5000 slarboseconds, the largest possible amount, and the apocalypse will come.

You are lucky enough to live on Jamcode X. The apocalypse came on Jamcode IX less than a year ago. But Jamcode X has a worrying prophecy of its own: "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 the optimum anniversary will occur. After studying the diary of a scientist from Jamcode IX, the scientists working on the problem came up with a theory.

The moment of reckoning is now, the moment you solve this problem. At some time $y \ge 0$ slarboseconds from now, the number of slarboseconds since each of the Great Events will be divisible by some maximum number $T$. The smallest $y$ that gives this largest possible $T$ is 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.

Compute the amount of time until the apocalypse comes. Remember the prophecy: the people of Jamcode X have been solving problems for two years and 64-bit integers have always been enough, but they might not be enough now or in the future.

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

Limits

• $1 \le C \le 100$
• $2 \le N \le 1000$
• $1 \le t_i \le 10^{50}$
• $t_i \ne t_j$ for at least one pair $i$, $j$.

For each test case, output one line in the form 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 every $i$.

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.