Tất cả bạn bè của bạn sẽ đi ăn tối tại một nhà hàng tối nay. Họ đều rất giỏi toán, nhưng họ cũng rất kỳ lạ: người bạn thứ \(a\) của bạn (bắt đầu từ 1) sẽ không vui trừ khi tổng chi phí của bữa ăn là một số nguyên dương và chia hết cho \(a\).

Các bạn của bạn lần lượt vào nhà hàng từng người một. Ngay khi có ai đó bước vào nhà hàng, nếu người đó không vui thì cả nhóm sẽ gọi phục vụ ngay lập tức.

Miễn là có ít nhất một người không vui trong nhà hàng, một trong những người không vui đó sẽ mua món đồ có giá thấp nhất để làm cho anh ta hoặc cô ta vui. Điều này sẽ tiếp tục cho đến khi không còn ai trong nhà hàng không vui, và sau đó người phục vụ sẽ rời đi. May mắn thay, nhà hàng bán đồ ăn ở mọi mức giá nguyên dương. Xem phần giải thích của ví dụ đầu tiên để biết thêm chi tiết.

Các bạn của bạn có thể chọn vào nhà hàng theo bất kỳ thứ tự nào. Sau khi người phục vụ đã được gọi, nếu có nhiều hơn một người không vui trong nhà hàng, bất kỳ ai trong số những người không vui đó đều có thể chọn mua một thứ gì đó trước. Cách thức thực hiện tất cả các lựa chọn đó có thể ảnh hưởng đến số lần nhóm gọi phục vụ.

Là chủ nhà hàng, bạn thuê một số người phục vụ rất mệt mỏi. Bạn muốn tính độ chênh lệch (spread) của những người bạn của mình: sự khác biệt giữa số lần tối đa họ có thể gọi phục vụ và số lần tối thiểu họ có thể gọi phục vụ.

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào cho biết số lượng bộ test, \(T\). \(T\) bộ test tiếp theo, mỗi bộ trên một dòng. Mỗi bộ test sẽ chứa một số nguyên \(N\), số lượng bạn bè mà bạn có.

Dữ liệu ra

Đối với mỗi bộ test, hãy xuất một dòng chứa "Case #x: y", trong đó x là số thứ tự của bộ test (bắt đầu từ 1) và y là độ chênh lệch cho bộ test đó.

Ràng buộc

• \(1 \le T \le 100\).
• \(1 \le N \le 1000\) (Dữ liệu nhỏ).
• \(1 \le N \le 10^{12}\) (Dữ liệu lớn).

Phân nhóm

Các giới hạn cho tập nhỏ và tập lớn được nêu ở trên.

Đ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ụ

4
1
3
6
16

Case #1: 0
Case #2: 1
Case #3: 2
Case #4: 5

Nguồn

Google Code Jam 2011, Vòng 2, bài Expensive Dinner.

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