Trò chơi này có thể chơi trên bất kỳ tập con \(S\) nào của các số nguyên dương. Một số trong \(S\) được coi là thuần khiết (pure) đối với \(S\) nếu, bắt đầu từ nó, bạn có thể liên tiếp lấy thứ hạng (rank) của nó trong \(S\), và nhận được một số cũng nằm trong \(S\), cho đến khi sau một số bước hữu hạn, bạn chạm đến số 1, số này không nằm trong \(S\).

Khi cho trước \(n\), có bao nhiêu cách để bạn chọn \(S\), một tập con của \(\{2, 3, \dots, n\}\), sao cho \(n\) là thuần khiết đối với \(S\)? Câu trả lời có thể là một số rất lớn, bạn cần đưa ra kết quả theo modulo 100003.

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\) dòng tiếp theo, mỗi dòng chứa một số nguyên duy nhất \(n\).

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ự bộ test (bắt đầu từ 1) và y là câu trả lời như mô tả ở trên.

Ràng buộc

• \(T \le 100\).

Phân nhóm

• Small dataset (Test set 1): \(2 \le n \le 25\).
• Large dataset (Test set 2): \(2 \le n \le 500\).

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

Case #1: 5
Case #2: 8

Nguồn

Google Code Jam 2010, Vòng 1B, bài Your Rank is Pure.

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