드러머 (스몰)

문제

드러머는 밴드에서 박자를 지키는 역할을 맡는다. 박자가 흔들리면 연주 전체가 무너진다.

당신은 인기 록 밴드의 보컬이다. 드러머가 프로 게이머가 되겠다며 밴드를 떠났고, 새 드러머를 당장 구해야 한다. 다행히 지원자는 넘친다. 그중에서 박자를 가장 일정하게 유지하는 사람을 골라야 한다.

오디션은 한 명씩 따로 본다. 지원자는 드럼 하나를 스틱으로 여러 번 친다. 박자가 완벽하다면 연속한 두 타격의 시간 간격이 모두 같고, 타격 시각은 $T_0,\ T_0+K,\ T_0+2K,\ \dots,\ T_0+(N-1)K$ 형태의 등차수열을 이룬다. 여기서 $T_0$ 와 $K$ 는 실수다.

사람이 완벽한 박자를 치기란 사실상 불가능하다. 그래서 지원자의 연주에는 오차 $E$ 가 생긴다. 오차가 $E$ 라는 말은, 모든 $i$ 에 대해 $|T_i - (T_0 + iK)| \le E$ 를 만족하는 $T_0$ 와 $K$ 가 존재한다는 뜻이다. 타격은 0번부터 센다.

지원자의 타격 시각이 주어질 때, 지원자가 노렸을 법한 완벽한 박자 전체를 통틀어 가능한 오차 $E$ 의 최솟값을 구하라.

입력

첫 줄에 테스트 케이스의 수 $T$ 가 주어진다. 이어서 각 테스트 케이스가 두 줄씩 주어지고, 한 테스트 케이스는 지원자 한 명의 오디션이다. 첫 줄에는 타격 횟수 $N$ 이 주어진다. 둘째 줄에는 지원자가 드럼을 친 시각 $N$ 개가 밀리초 단위 정수로, 공백을 사이에 두고 증가하는 순서로 주어진다.

제한

$1 \le T \le 100$
$2 \le N \le 10$
$0 \le T_i \le 100$
$T_i < T_{i+1}$

출력

각 테스트 케이스마다 Case #x: E 형식으로 한 줄씩 출력한다. $x$ 는 1부터 시작하는 테스트 케이스 번호이고, $E$ 는 가능한 오차의 최솟값이다.

$E$ 는 항상 유리수이므로 기약분수로 출력한다. $E = p/q$ 이고 $p \ge 0$ , $q \ge 1$ , $\gcd(p, q) = 1$ 일 때 p/q를 출력하되, $q$ 가 1이면 p만 출력한다. 오차가 0이면 0을, 4분의 3이면 3/4을 출력한다.