드러머 (라지)

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

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

오디션은 지원자 한 명씩 따로 진행한다. 지원자는 북 하나를 스틱으로 여러 번 두드린다. 완벽한 박자라면 연속한 두 타격의 시간 간격이 모두 같고, 타격 시각은 등차수열 $T_0,\ T_0 + K,\ T_0 + 2K,\ \dots,\ T_0 + (N-1)K$ 를 이룬다.

사람이 완벽한 박자를 내기는 사실상 불가능하다. 그래서 지원자의 연주는 어떤 완벽한 박자를 기준으로 각 타격 시각이 최대 $E$ 만큼 어긋난다. 더 정확히 말하면, 실수 $a$ 와 실수 $K \ge 0$ 을 골라 완벽한 박자를 $S_i = a + iK$ 로 두었을 때 그 박자에 대한 오차는

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

이다. 지원자의 타격 시각 $T_0, T_1, \dots, T_{N-1}$ 이 주어질 때, $a$ 와 $K$ 를 자유롭게 고를 수 있다고 하고 오차 $E$ 의 최솟값을 구하라.

첫 줄에 테스트 케이스의 수 $T$ 가 주어진다. 이어서 $T$ 개의 테스트 케이스가 주어지고, 각각은 지원자 한 명의 오디션을 나타내며 두 줄로 이루어진다. 첫 줄에는 타격 횟수 $N$ 이 주어진다. 둘째 줄에는 지원자가 북을 두드린 시각 $N$ 개가 밀리초 단위 정수로 공백을 사이에 두고 주어진다. 시각은 오름차순으로 주어진다.

제한

• $1 \le T \le 100$
• $2 \le N \le 50\,000$
• $0 \le T_i \le 10^6$
• $T_i \le T_{i+1}$ (같은 시각이 연달아 나올 수 있다)

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

최솟값 $E$ 는 항상 유리수이다. $E$ 를 기약분수 p/q 꼴로 출력한다. $p$ 는 0 이상의 정수, $q$ 는 2 이상의 정수이고 두 수는 서로소여야 한다. 분모가 1이면 분수 대신 정수 $p$ 만 출력한다. 예를 들어 오차의 최솟값이 $3/4$ 이면 3/4 를, $2$ 이면 2 를 출력한다.