Numbers

Đề bài

Trong bài toán này, bạn phải tìm ba chữ số cuối cùng trước dấu phẩy thập phân của số \((3 + \sqrt{5})^n\).

Ví dụ, khi \(n = 5\), \((3 + \sqrt{5})^5 = 3935.73982...\) Câu trả lời là \(935\).

Với \(n = 2\), \((3 + \sqrt{5})^2 = 27.4164079...\) Câu trả lời là \(027\).

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 theo sau, mỗi bộ trên một dòng riêng biệt. Mỗi bộ test chứa một số nguyên dương \(n\).

Dữ liệu ra

Với mỗi bộ test, bạn nên xuất ra:

Case #X: Y

trong đó \(X\) là số thứ tự của bộ test và \(Y\) là ba chữ số nguyên cuối cùng của số \((3 + \sqrt{5})^n\). Trong trường hợp số đó có ít hơn ba chữ số nguyên, hãy thêm các số không ở đầu để đầu ra của bạn chứa đúng ba chữ số.

Ràng buộc

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

Phân nhóm

• Tập kiểm tra 1 (Visible): \(2 \le n \le 30\)
• Tập kiểm tra 2 (Hidden): \(2 \le n \le 2000000000\)

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

2
5
2

Case #1: 935
Case #2: 027

Nguồn

Google Code Jam 2008, Vòng 1A, bài Numbers.

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