Người đánh trống đóng vai trò rất quan trọng trong bất kỳ ban nhạc nào — giữ nhịp. Nếu nhịp điệu của người đánh trống không đều, nó có thể làm hỏng cả buổi biểu diễn.

Bạn là ca sĩ chính của một ban nhạc rock rất nổi tiếng, và bạn đang gặp một chút vấn đề. Người đánh trống của bạn vừa rời ban nhạc để trở thành một game thủ chuyên nghiệp. Bạn cần tìm một người đánh trống mới ngay lập tức. May mắn thay, không thiếu các ứng viên. Mọi người đều muốn có cơ hội tham gia ban nhạc của bạn. Nhiệm vụ của bạn là tìm ra người đánh trống giỏi nhất trong số các ứng viên, và bạn muốn người có thể giữ nhịp ổn định nhất.

Kế hoạch của bạn như sau. Bạn sẽ yêu cầu mỗi ứng viên thử giọng riêng lẻ. Trong buổi thử giọng, ứng viên sẽ chơi một chiếc trống bằng cách gõ vào nó bằng dùi trống vài lần. Lý tưởng nhất là khoảng thời gian giữa các lần gõ liên tiếp phải hoàn toàn giống nhau, tạo ra một nhịp điệu hoàn hảo. Trong một nhịp điệu hoàn hảo, các mốc thời gian của các lần gõ trống sẽ tuân theo một cấp số cộng như sau: \(T_0, T_0 + K, T_0 + 2 \times K, \dots, T_0 + (N - 1) \times K\).

Tất nhiên, trong thực tế, con người gần như không thể tạo ra một nhịp điệu hoàn hảo. Do đó, mỗi ứng viên đánh trống sẽ tạo ra một nhịp điệu có sai số \(E\), sao cho mỗi \(T_i\) khác biệt tối đa \(E\) so với một nhịp điệu hoàn hảo nào đó. Cho một chuỗi các lần gõ trống của một ứng viên, hãy tìm giá trị \(E\) nhỏ nhất có thể trong số tất cả các nhịp điệu hoàn hảo mà ứng viên đó có thể đã cố gắng chơi.

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào cho biết số lượng bộ thử nghiệm, \(T\). \(T\) bộ thử nghiệm tiếp theo. Mỗi bộ gồm hai dòng và đại diện cho buổi thử giọng của một ứng viên. Dòng đầu tiên chứa một số nguyên duy nhất — \(N\). Dòng tiếp theo chứa \(N\) số nguyên cách nhau bởi dấu cách — các mốc thời gian, tính bằng mili giây, của các lần gõ trống do ứng viên thực hiện. Các mốc thời gian được cho theo thứ tự tăng dần.

Dữ liệu ra

Đối với mỗi bộ thử nghiệm, hãy xuất một dòng chứa "Case #x: \(E\)", trong đó x là số thứ tự bộ thử nghiệm (bắt đầu từ 1) và \(E\) là số nhỏ nhất trong số tất cả các số có thể mô tả sai số của chuỗi gõ trống của ứng viên.

Câu trả lời của bạn sẽ được coi là chính xác nếu nó nằm trong khoảng sai số tuyệt đối hoặc tương đối là \(10^{-6}\) so với câu trả lời đúng.

Ràng buộc

• \(1 \le T \le 100\).

Phân nhóm

• Nhóm 1 (Visible):

• \(2 \le N \le 10\).

• \(0 \le T_i \le 100\).

• Nhóm 2 (Hidden):

• Đối với 90% các bộ thử nghiệm, \(2 \le N \le 1000\).

• Đối với tất cả các bộ thử nghiệm, \(2 \le N \le 50000\).
• \(0 \le T_i \le 10^6\).

Điểm các phân nhóm

Mỗi Test Set tương ứng với một subtask trên LQDOJ. Bảng dưới đây giữ nguyên điểm chính thức của Google Code Jam và quy đổi tỷ lệ trên tổng điểm của bài.

Ví dụ

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

Nguồn

Google Code Jam 2013, Chung kết thế giới, bài Drummer.

Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.