Hiện nay, cuộc chiến giữa hai nước RU và UC ngày càng khốc liệt. Nước RU sử dụng những quả bom chùm có khối lượng lên đến \(10^{12}\) đơn vị khối lượng, có sức mạnh công phá bằng tổng của các ước nguyên dương của nó. Nước UC muốn bảo vệ đất nước của mình thì với mỗi quả bom chùm của RU bắn ra phải đối kháng lại bằng quả bom có sức công phá tương đương.

Bạn là người lập trình, hãy thống kê lại với q quả bom chùm khối lượng lần lượt: a₁, a₂, …, a_q sẽ có sức công phá tương ứng là bao nhiêu nhé!

Dữ liệu:

+ Dòng thứ nhất chứa duy nhất số nguyên dương q (\(q\ \leq \ 10\)⁶).

+ Dòng thứ hai chứa q số nguyên dương: a₁, a₂,…, a_q, số thứ i có khối lượng là a_i

\(\mathbf{(}1\ \leq \ i\ \leq \ q\mathbf{)}\).

Kết quả: Ghi \(q\) số, số thứ i thể hiện sức mạnh công phá của quả bom có khối lượng a_i. Các số in ra phân cách nhau bởi một dấu cách.

Ví dụ:

Giải thích:

Gọi G(x) là tổng các ước của x.

Test ví dụ 1 có:

\(G(2) = \ 1\ + \ 2\ = \ 3;\ G(4) = \ 1\ + \ 2\ + \ 4\ = \ 7;\ G(10) = \ 1\ + \ 2\ + \ 5\ + \ 10\ = \ 18; \)\[G(9)\ = \ 1\ + \ 3\ + \ 9\ = \ 13.\]

Test ví dụ 2 có: \(\mathbf{\ \ \ }\)

\[{G(10)\ = \ 18;\ G(11)\ = \ 1\ + \ 11\ = \ 12; }{G(12)\ = \ 1\ + \ 2\ + \ 3\ + \ 4\ + \ 6\ + \ 12\ = \ 28;\ G(13)\ = \ 1\ + \ 13\ = \ 14}\]

Ràng buộc:

Subtask 1: (40% số điểm): \(q\ \leq \ 10\)⁴\(;\ a\)_i\(\ \leq \ 10\)³\(\ (1\ \leq \ i\ \leq \ q)\)

Subtask 2: (40% số điểm): \(10\)⁴\(\ < q\ \leq \ 10\)⁵\(;\ a\)_i\(\ \leq \ 10\)⁶\(\ (1\ \leq \ i\ \leq \ q)\)

Subtask 3: (20% số điểm): \(10\)⁵\(\ < q\ \leq \ 10\)⁶\(;\ a\)_i \(\leq \ 10\)¹²\(\ (1\ \leq \ i\ \leq \ q);\ a\)_i+1\(\ = \ a\)_i \(+ \ 1\ (1 \leq i < q)\)