The drummer has a very important role in any band -- keeping the rhythm. If the drummer's rhythm is uneven, it can ruin the entire performance.
You are the lead singer of a very popular rock band, and you have a bit of a problem. Your drummer has just quit the band to become a professional video gamer. You need to find a new drummer immediately. Fortunately, there is no shortage of candidates. Everyone wants a chance to join your band. Your task is to find the best drummer among the candidates, and you want the person who can keep the most consistent rhythm.
Your plan is as follows. You will ask each candidate to audition
individually. During the audition, the candidate will play one drum by
striking it with a drum stick several times. Ideally, the time
difference between consecutive strikes should be exactly the same,
producing a perfect rhythm. In a perfect rhythm, the drum strikes will
have time stamps that follow an arithmetic progression like this:
In real life, of course, it is nearly impossible for a human to produce a
perfect rhythm. Therefore, each candidate drummer will produce a rhythm
that has an error E, such that each
The first line of the input gives the number of test cases, T. T test cases follow. Each one consists of two lines and represents the audition of one candidate. The first line contains a single integer -- N. The next line contains N integers separated by spaces -- the time stamps, in milliseconds, of the drum strikes played by the candidate. The time stamps are in increasing order.
For each test case, output one line containing "Case #x: E", where x is the case number (starting from 1) and E is the smallest among all possible numbers that describe the error of the candidate's drum strike sequence.
Your answer will be considered correct if it is within an absolute or relative error of 10-6 of the correct answer. See the FAQ for an explanation of what that means, and what formats of floating-point numbers we accept.
1 ≤ T ≤ 100.
2 ≤ N ≤ 10.
0 ≤ Ti ≤ 100.
For 90% of the test cases, 2 ≤ N ≤ 1000.
For all test cases, 2 ≤ N ≤ 50000.
0 ≤ Ti ≤ 106.
3 2 10 70 4 0 10 19 30 6 2 5 10 15 20 24
Case #1: 0 Case #2: 0.5 Case #3: 0.75