Trò chơi

Năm nay, kỳ thi học sinh giỏi Duyên hải và Đồng bằng Bắc Bộ được tổ chức rất hoành tráng tại tỉnh Thái Nguyên. Thầy Hiếu đang suy nghĩ làm thế nào để có được sân chơi thật bổ ích cho các em học sinh tham dự. Là dân tin nên thầy Hiếu có một trò chơi khá hay để các em cùng tham dự:

Bạn đang chơi một trò chơi một người chơi, trong đó bạn phải chơi ${10}^{12}$ màn chơi khác nhau để tiêu diệt ${10}^{12}$ con Boss khác nhau. Màn chơi thứ $i$ sẽ xuất hiện con Boss thứ $i$ có chỉ số sức mạnh bằng tổng các ước nguyên dương của $i$.

Bạn đang cần xem lại thống kê của $q$ màn chơi $a_1,a_2,\dots ,a_q$.

Yêu cầu: Hãy cho biết sức mạnh của Boss trong mỗi màn chơi cần xem.

Dữ liệu vào

• Dòng thứ nhất chứa số nguyên dương $q$.
• Dòng thứ hai chứa $q$ số nguyên dương $a_1,a_2,\dots ,a_q$.

Dữ liệu ra

In ra $q$ số nguyên trên cùng một dòng, số thứ $i$ là sức mạnh của Boss thứ $a_i$ ($1\le i\le q$). Các số được phân tách bởi một dấu cách.

Ràng buộc

• $1\le q\le {10}^6$, $1\le a_i\le {10}^{12}$.
• Mỗi test thỏa mãn ràng buộc của ít nhất một subtask dưới đây (nói riêng, nếu có $a_i>{10}^6$ hoặc $q>{10}^5$ thì $a_{i+1}=a_i+1$ với mọi $1\le i<q$).

Subtasks

• Subtask 1 ($15\%$ số điểm): $q\le {10}^4$; $a_i\le {10}^3$ ($1\le i\le q$).
• Subtask 2 ($25\%$ số điểm): $q\le {10}^5$; $a_i\le {10}^5$ ($1\le i\le q$).
• Subtask 3 ($35\%$ số điểm): $q\le {10}^5$; $a_i\le {10}^6$ ($1\le i\le q$).
• Subtask 4 ($25\%$ số điểm): $q\le {10}^6$; $a_i\le {10}^{12}$ ($1\le i\le q$); $a_{i+1}=a_i+1$ ($1\le i<q$).

Ví dụ