Trên Jamcode IX, ba Đại Sự Kiện xảy ra cách đây 26000, 11000 và 6000 slarbosecond. Sau 4000 slarbosecond, thời gian kể từ cả ba sự kiện đều là bội của 5000 — giá trị lớn nhất có thể — và “tận thế” đến.

Bạn sống trên Jamcode X, nơi có lời tiên tri: sau thời khắc phán xét, vào ngày kỷ niệm tối ưu đầu tiên của \(N\) Đại Sự Kiện, tận thế sẽ đến; 64 bit không cứu được bạn. Các sự kiện đã xảy ra và thời điểm được đo chính xác tới slarbosecond.

Thời khắc phán xét là hiện tại. Tại thời điểm \(y\ge0\) kể từ bây giờ, số slarbosecond kể từ mỗi sự kiện phải chia hết cho cùng một số nguyên lớn nhất có thể \(T\). Trong các \(y\) đạt \(T\) lớn nhất ấy, ngày kỷ niệm tối ưu là \(y\) nhỏ nhất. Hãy tính thời gian còn lại.

Dữ liệu vào

Dòng đầu là số test \(C\). Mỗi dòng tiếp theo gồm \(N\) rồi \(N\) số \(t_i\), số slarbosecond kể từ sự kiện \(i\).

Dữ liệu ra

In Case #x: y, trong đó \(y\) nhỏ nhất sao cho mọi \(t_i+y\) là bội của hệ số nguyên lớn nhất \(T\).

Ràng buộc

• \(1\le C\le100\); tồn tại \(i,j\) với \(t_i e t_j\).
• Thời gian 30 giây mỗi bộ; bộ nhớ 1 GB.

Phân nhóm

• Nhỏ: \(2\le N\le3\), \(1\le t_i\le10^8\).
• Lớn: \(2\le N\le1000\), \(1\le t_i\le10^{50}\).

Đ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
3 26000000 11000000 6000000
3 1 10 11
2 800000000000000000001 900000000000000000001

Case #1: 4000000
Case #2: 0
Case #3: 99999999999999999999

Hậu truyện

May thay, “tận thế” hóa ra là bản dịch nhầm của “bữa tiệc khổng lồ”. Không ai ở Jamcode IX báo lại vì họ đang vui quá.

Nguồn

Google Code Jam 2010, Vòng loại, bài Fair Warning.

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