Below is the description of a problem called 'Fair Warning', from 'Google Code Jam - 2010':

Problem

-------

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

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 ti, the number of slarboseconds since Great Event i occurred.

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 ti + y is a multiple of the largest possible integer factor T for all i.

Limits

------

1 ≤ C ≤ 100.

ti ≠ tj for some i, j.

Small dataset

-------------

2 ≤ N ≤ 3.

1 ≤ ti ≤ 108.

Large dataset

-------------

2 ≤ N ≤ 1000.

1 ≤ ti ≤ 1050.

Sample Input

------------

3

3 26000000 11000000 6000000

3 1 10 11

2 800000000000000000001 900000000000000000001

Output

------

Case #1: 4000000

Case #2: 0

Case #3: 99999999999999999999

Below is my java solution:

- GCJ 2014 - 'Deceitful War'
- GCJ 2014 - 'Cookie Clicker Alpha' Problem
- GCJ 2014 - Magic Trick
- GCJ 2013 - Fair And Square
- GCJ 2013 - Tic-Tac-Toe-Tomek
- GCJ 2012 - Recycled Numbers
- GCJ 2012 - Dancing With Googlers
- GCJ 2012 - Speaking In Tongues
- GCJ 2011 - Magicka
- GCJ 2011 - Bot Trust
- GCJ 2010 - Fair Warning
- GCJ 2010 - Snapper Chain
- Odd Man Out - GCJ 2010 (Africa)
- Store Credit - GCJ 2010 (Africa)
- T9Spelling - GCJ 2010 (Africa)
- Reverse Words - GCJ 2010 (Africa)
- All Your Base - GCJ 2009
- Alien Language - GCJ 2009
- Google Code Jam 2008 - Minimum Scalar Product
- GCJ 2008 - Alien Numbers
- Playing With Googol
- Google Billboard Puzzle
- Euler's Number (e) to 10000 digits
- Spiral Walking

- GCJ 2014 - 'Deceitful War'
- GCJ 2014 - 'Cookie Clicker Alpha' Problem
- GCJ 2014 - Magic Trick
- GCJ 2013 - Fair And Square
- GCJ 2013 - Tic-Tac-Toe-Tomek
- GCJ 2012 - Recycled Numbers
- GCJ 2012 - Dancing With Googlers
- GCJ 2012 - Speaking In Tongues
- GCJ 2011 - Magicka
- GCJ 2011 - Bot Trust
- GCJ 2010 - Fair Warning
- GCJ 2010 - Snapper Chain
- Odd Man Out - GCJ 2010 (Africa)
- Store Credit - GCJ 2010 (Africa)
- T9Spelling - GCJ 2010 (Africa)
- Reverse Words - GCJ 2010 (Africa)
- All Your Base - GCJ 2009
- Alien Language - GCJ 2009
- Google Code Jam 2008 - Minimum Scalar Product
- GCJ 2008 - Alien Numbers
- Playing With Googol
- Google Billboard Puzzle
- Euler's Number (e) to 10000 digits
- Spiral Walking

- Recursion Depth - Java
- RESTFul Web Service - Seam Component Injection
- Micro-benchmarking Java Code With Caliper
- JSF & Highcharts (Javascript Chart Library)
- Add 'Syntactic Sugar' With 'Fluent Interface'
- Priority Queue in Java
- Compile Java Files At Runtime
- Missing Number
- Guice - AOP (Aspect Oriented Programming)
- Creating Executable Jar File With Maven Shade Plugin
- Java - Looping Through A Range of BigInteger Values
- Create Your Own Dependency Injection Framework
- Google Guice - Example
- Guice Grapher - Example
- Using Richfaces 'Suggestion Box' As Combo Box
- Hashcode Of A String In Java
- Richfaces - Modal Panel As A Wizard
- Jasper Reports - Thermometer Report
- Jasper Reports - Gantt Chart
- Jasper Reports - Example
- Seam - Load i18n Messages From Database
- Autoboxing In Java & Bug Patterns
- Dont Smack The Stack (Deal With Stack Overflow Exceptions)

The views expressed on this blog are my personal views and do not reflect the views of
my employer or campaigns I am supporting.

All sample code is provided for illustrative purposes only. These examples have not been thoroughly tested under all conditions. The writer therefore, cannot guarantee or imply reliability, serviceability, or function of these programs.

All programs contained herein are provided to you "AS IS" without any warranties of any kind. The implied warranties of non-infringement, merchantability and fitness for a particular purpose are expressly disclaimed.

All sample code is provided for illustrative purposes only. These examples have not been thoroughly tested under all conditions. The writer therefore, cannot guarantee or imply reliability, serviceability, or function of these programs.

All programs contained herein are provided to you "AS IS" without any warranties of any kind. The implied warranties of non-infringement, merchantability and fitness for a particular purpose are expressly disclaimed.