Drummer (Large)

A drummer keeps the rhythm for the band. If the rhythm wobbles, the whole performance falls apart.

You are the lead singer of a popular rock band, and you have a problem. Your drummer just quit to become a professional gamer, so you need a replacement right now. Candidates are plentiful. Your job is to find the one who keeps the steadiest rhythm.

You audition the candidates one at a time. During an audition, a candidate strikes a single drum with a stick several times. In a perfect rhythm the gap between consecutive strikes is always the same, so the strike times form the arithmetic progression $T_0,\ T_0 + K,\ T_0 + 2K,\ \dots,\ T_0 + (N-1)K$.

No human plays a perfect rhythm. Each candidate's performance differs from some perfect rhythm by at most $E$ at every strike. More precisely, pick a real number $a$ and a real number $K \ge 0$, let the perfect rhythm be $S_i = a + iK$, and define the error against that rhythm as

$E = \max_{0 \le i < N} |T_i - S_i|$

Given the strike times $T_0, T_1, \dots, T_{N-1}$ of one candidate, find the smallest error $E$ over all choices of $a$ and $K$.

The first line contains the number of test cases $T$. Each of the $T$ test cases describes one audition and takes two lines. The first line contains the number of strikes $N$. The second line contains $N$ integers separated by spaces, the strike times in milliseconds. The times are given in increasing order.

Limits

• $1 \le T \le 100$
• $2 \le N \le 50\,000$
• $0 \le T_i \le 10^6$
• $T_i \le T_{i+1}$ (two strikes can share the same time)

For each test case, print one line in the form Case #x: E, where $x$ is the test case number starting from 1 and $E$ is the smallest error the candidate could have.

The smallest error is always a rational number. Print $E$ as the irreducible fraction p/q, where $p$ is a nonnegative integer, $q$ is an integer greater than 1, and the two are coprime. If the denominator is 1, print only the integer $p$ instead of a fraction. For example, print 3/4 for an error of $3/4$, and 2 for an error of $2$.